1.01背包

题目描述

有 n 个重量个价值分别为 w_i, v_i 的物品。
从这些物品中选出总重量不超过 W 的物品，使其总价值最大。

输入：
1 // 用例数
5 10 // 物品数背包容量 N <= 1000 , V <= 1000
1 2 3 4 5 //价值
5 4 3 2 1 //重量

输出：14

1.1 二维DP

DP定义：dp[i][j] 从前 i 个物品中选取总重量不超过 j 的物品时总价值的最大值；
DP初始：dp[0][j] = 0;
DP转移：
- dp[i][j] = dp[i-1][j] if(j<w[i]), 当前剩余容量不够放下第i个物品
- dp[i][j] = max(dp[i-1][j], dp[i-1][j-w[i]] + v[i])

int max_value1(vector<int> v, vector<int> w, int V, int N){
    vector<vector<int>> dp(N+1, vector<int>(V+1, 0));
    for(int i=1;i<=N;i++){
        for(int j=0;j<=V;j++){
            if(w[i]>j) dp[i][j] = dp[i-1][j];
            else dp[i][j] = max(dp[i-1][j], dp[i-1][j-w[i]]+v[i]);
        }
    }
    return dp[N][V];
}

int main(){
    int T;
    cin >> T;

    int N, V;
    cin >> N >> V;
    vector<int> v, w;
    v.push_back(0);
    w.push_back(0);
    int n;
    for(int i=0;i<N;i++){
        cin >> n;
        v.push_back(n);
    }

    for(int i=0;i<N;i++){
        cin >> n;
        w.push_back(n);
    }

    while(T){
        int res = max_value2(v, w, V, N);
        cout << res << endl;
        T--;
    }

    return 0;
}

1.2 一维DP

DP定义：dp[j] 总重量不超过 j 的物品时总价值的最大值；
DP初始：dp[j] = 0;
DP转移：dp[j] = max(dp[j], dp[j-w[i]] + v[i]) if(j>w[i])

int max_value2(vector<int> v, vector<int> w, int V, int N){
    vector<int> dp(V+1, 0);
    for(int i=1;i<=N;i++){
        for(int j=V;j>=w[i];j--){
            dp[j] = max(dp[j], dp[j-w[i]]+v[i]);
        }
    }
    return dp[V];
}

2.完全背包

题目描述

01 背包中每个物品只有一个，所以只存在选或不选；
完全背包中每个物品可以选取任意件。

一维DP

DP定义：dp[j] 总重量不超过 j 的物品时总价值的最大值；
DP初始：dp[j] = 0;
DP转移：dp[j] = max(dp[j], dp[j-w[i]] + v[i]) if(j>w[i])

int max_value(vector<int> v, vector<int> w, int V, int N){
    vector<int> dp(V+1, 0);
    for(int i=1;i<=N;i++){
        for(int j=w[i];j<=V;j++){
            dp[j] = max(dp[j], dp[j-w[i]]+v[i]);
        }
    }
    return dp[V];
}

3. leetcode322-零钱兑换

题目描述

给定不同面额的硬币 coins 和一个总金额 amount。编写一个函数来计算可以凑成总金额所需的最少的硬币个数。如果没有任何一种硬币组合能组成总金额，返回 -1。

输入: coins = [1, 2, 5], amount = 11
输出: 3
解释: 11 = 5 + 5 + 1

DP求解

DP定义：dp[i] : 组成总金额i时的最少硬币数
DP初始：
- dp[0] = 0;
- dp[i] = amount+1， i != 0
DP转移：dp[i] = min(dp[i-coins[j]]+1, dp[i]) ,if i>=coins[j];

class Solution {
public:
    int coinChange(vector<int>& coins, int amount) {
        vector<int> dp(amount+1, amount+1);
        dp[0] = 0;
        sort(coins.begin(), coins.end());
        for(int i=0;i<=amount;i++){
            for(int j=0;j<coins.size();j++){
                if(i - coins[j]>=0) dp[i] = min(dp[i], 1 + dp[i - coins[j]]);
            }
        }
        return dp[amount]>amount ? -1 : dp[amount];
    }
};

4. leetcode518-零钱兑换II

题目描述

给定不同面额的硬币和一个总金额。写出函数来计算可以凑成总金额的硬币组合数。假设每一种面额的硬币有无限个。

输入: amount = 5, coins = [1, 2, 5]
输出: 4
解释: 有四种方式可以凑成总金额:
5=5
5=2+2+1
5=2+1+1+1
5=1+1+1+1+1

DP求解

DP定义：dp[i] : 组成总金额 i 的方式
DP初始：dp[0] = 1
DP转移：dp[i]=dp[i]+dp[i-coin];

class Solution {
public:
    int change(int amount, vector<int>& coins) {
        vector<int> dp(amount+1, 0);
        dp[0] = 1;
        for(auto coin:coins ){
            for(int i=coin;i<=amount;i++){
                dp[i] += dp[i-coin];
            }
        }
        return dp[amount];
    }
};

5. 最长公共子序列

题目描述

对于两个字符串，请设计一个高效算法，求他们的最长公共子序列的长度，这里的最长公共子序列定义为有两个序列U1,U2,U3...Un和V1,V2,V3...Vn,其中Ui&ltUi+1，Vi&ltVi+1。且A[Ui] == B[Vi]。
给定两个字符串A和B，同时给定两个串的长度n和m，请返回最长公共子序列的长度。保证两串长度均小于等于300。

输入："1A2C3D4B56",10,"B1D23CA45B6A",12
输出：6

DP求解

DP定义：dp[i][j] : A[0:i]和B[0:j]的最长公共子序列的长度
DP初始：dp[i][j] = 0 , i=0 or j=0
DP转移：
- dp[i][j]=dp[i-1][j-1]+1 if A[i-1]==B[j-1];
- dp[i][j]=dp[i][j] = max(dp[i-1][j], dp[i][j-1]);

class LCS {
public:
    int findLCS(string A, int n, string B, int m) {
        vector<vector<int>> dp(n+1, vector<int>(m+1, 0));

        for(int i=1;i<=n;i++){
            for(int j=1;j<=m;j++){
                if(A[i-1]==B[j-1]) dp[i][j] = dp[i-1][j-1] + 1;
                else dp[i][j] = max(dp[i-1][j], dp[i][j-1]);
            }
        }
        return dp[n][m];
    }
};

6. 最长公共子串

题目描述

对于两个字符串，请设计一个时间复杂度为O(m * n)的算法(这里的m和n为两串的长度)，求出两串的最长公共子串的长度。这里的最长公共子串的定义为两个序列U1,U2,..Un和V1,V2,...Vn，其中Ui + 1 == Ui+1,Vi + 1 == Vi+1，同时Ui == Vi。给定两个字符串A和B，同时给定两串的长度n和m。

测试样例：
输入："1AB2345CD",9,"12345EF",7
输出：返回：4

DP求解

DP定义：dp[i][j] : A[0:i]和B[0:j]的最长公共子序列的长度
DP初始：dp[i][j] = 0 , i=0||j=0
DP转移：dp[i][j]=dp[i-1][j-1]+1 if A[i-1]==B[j-1];

class LongestSubstring {
public:
    int findLongest(string A, int n, string B, int m) {
        vector<vector<int>> dp(n+1, vector<int>(m+1, 0));
        int length = 0;
        for(int i=1;i<=n;i++){
            for(int j=1;j<=m;j++){
                if(A[i-1]==B[j-1]) dp[i][j] = dp[i-1][j-1] + 1;
                length = max(length, dp[i][j]);
            }
        }
        return length;
    }
};

7. leetcode300-最长上升子序列

题目描述

给定一个无序的整数数组，找到其中最长上升子序列的长度。

输入: [10,9,2,5,3,7,101,18]
输出: 4
解释: 最长的上升子序列是 [2,3,7,101]，它的长度是 4。

可能会有多种最长上升子序列的组合，你只需要输出对应的长度即可。

DP求解

DP定义：dp[i] : 长度为 i 的 LIS 的最小尾元素
DP初始：dp[i][j] = 0 , i=0||j=0
DP转移：
- 二分查找 nums[j] 在 dp 中的lower_bound 位置
  - lower_bound 位置指的是序列中第一个大于等于 nums[j] 的元素所在的位置
- 如果在末尾，则插入；反之则替换

class Solution {
public:
    int lengthOfLIS(vector<int>& nums) {
        vector<int> dp;
        for(int i=0;i<nums.size();i++){
            int k = lower_bound(dp.begin(), dp.end(), nums[i]) - dp.begin();
            if(lower_bound(dp.begin(), dp.end(), nums[i]) != dp.end()) dp[k] = nums[i];
            else dp.push_back(nums[i]);
        }
        return dp.size();
    }
};

8. leetcode516-最长回文子序列

题目描述

给定一个字符串s，找到其中最长的回文子序列。可以假设s的最大长度为1000。

输入: "bbbab"
输出: 4

DP求解

DP定义：dp[i][j] : 字符串 s 在区间 [i:j] 上的子串的回文序列长度
DP初始：dp[i][i] = 1
DP转移：

dp[i][j] = dp[i+1][j-1] + 2, if s[i] == s[j]
dp[i][j] = max(dp[i+1][j], dp[i][j-1]), else
因为dp[i][j]=dp[i+1][j-1],所以 i 需要从字符串尾部开始遍历，即逆序。

class Solution {
public:
    int longestPalindromeSubseq(string s) {
        int n=s.size();
        vector<vector<int>> dp(n, vector<int>(n, 0));

        for(int i=0;i<n;i++) dp[i][i] = 1;

        for(int i=n-1;i>=0;i--){
            for(int j=i+1;j<n;j++){
                if(s[i]==s[j]) dp[i][j] = dp[i+1][j-1] + 2;
                else dp[i][j] = max(dp[i+1][j], dp[i][j-1]);
            }
        }

        return dp[0][n-1];
    }
};

9. leetcode5-最长回文子串序列

题目描述

给定一个字符串 s，找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。

输入: "babad"
输出: "bab"
注意: "aba" 也是一个有效答案。

DP求解

DP定义：dp[i][j] : 字符串 s 在区间 [i:j] 上的子串是否是一个回文串
DP初始：dp[i][i] = true
DP转移：

dp[i][j] = dp[i+1][j-1], if s[i] == s[j]
dp[i][j] = false, else
用length记录最长长度并用start_index记录子串最长子串的开始位置。

class Solution {
public:
    string longestPalindrome(string s) {
        int n=s.size();
        vector<vector<bool>> dp(n, vector<bool>(n, false));
        for(int i=0;i<n;i++) dp[i][i] = true;

        int length=1;
        int start_index=0;

        for(int i=n-1;i>=0;i--){
            for(int j=i+1;j<n;j++){
                if(j-i<2) dp[i][j] = (s[i]==s[j]) ? true : false;
                else if(s[i]==s[j]) dp[i][j] = dp[i+1][j-1];
                if(dp[i][j]&&j-i+1>length){
                    start_index = i;
                    length = j - i + 1;
                }
            }
        }
        return s.substr(start_index, length);
    }
};

10. leetcode-53-最大连续子序列和

题目描述

给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。

输入: [-2,1,-3,4,-1,2,1,-5,4],
输出: 6
解释: 连续子数组 [4,-1,2,1] 的和最大，为 6。

DP求解

DP定义：dp[i]: 序列 nums 在区间 [:i] 上的最大子序列
DP初始：dp[0] = nums[0]
DP转移:

dp[i] = dp[i-1] + nums[i], dp[i-1]>0
dp[i] = nums[i], else

res用以记录最大值。注意到每次递归实际只用到了 dp[i-1]，因此实际只用一个变量即可。

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        int max_num=INT_MIN;
        int temp=0;

        for(auto num:nums){
            if(temp>0) temp += num;
            else temp = num;

            max_num = max(max_num, temp);
        }
        return max_num;
    }
};

11. leetcode72-编辑距离

题目描述

给定两个单词 word1 和 word2，计算出将 word1 转换成 word2 所使用的最少操作数。你可以对一个单词进行如下三种操作：插入一个字符；删除一个字符；替换一个字符

输入: word1 = "horse", word2 = "ros"
输出: 3
解释:
horse -> rorse (将 'h' 替换为 'r')
rorse -> rose (删除 'r')
rose -> ros (删除 'e')

DP求解

DP定义：dp[i][j]: 将 word1[0:i] 转换为 word2[0:j] 的最少操作数
DP初始：

dp[i][0] = i , 每次从 word1 删除一个字符
dp[0][j] = j , 每次从 word2 删除一个字符

DP转移:

dp[i][j] = dp[i-1][j-1] , if word1[i] = word2[j]
dp[i][j] = min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) + 1, else

class Solution {
public:
    int minDistance(string word1, string word2) {
        int m = word1.size();
        int n = word2.size();
        vector<vector<int>> dp(m+1, vector<int>(n+1, 0));
        for(int i=0;i<=m;i++) dp[i][0] = i;
        for(int i=0;i<=n;i++) dp[0][i] = i;

        for(int i=1;i<=m;i++){
            for(int j=1;j<=n;j++){
                if(word1[i-1]==word2[j-1]) dp[i][j] = dp[i-1][j-1];
                else dp[i][j] = min(dp[i-1][j-1], min(dp[i-1][j], dp[i][j-1])) + 1;
            }
        }
        return dp[m][n];
    }
};

12. 最大正方形

题目描述

在一个由 0 和 1 组成的二维矩阵内，找到只包含 1 的最大正方形，并返回其面积。

输入:
1 0 1 0 0
1 0 1 1 1
1 1 1 1 1
1 0 0 1 0
输出: 4

DP求解

DP定义：dp[i][j]: 以 matrix[i][j] 为正方形右下角所能找到的最大正方形的边长
DP初始：

dp[i][0] = matrix[i][0] ,
dp[0][j] = matrix[0][j] ,

DP转移:

dp[i][j] = min({dp[i-1][j], dp[i-1][j], dp[i-1][j-1], }) +1, if matrix[i][j] == '1'
dp[i][j] = 0, else

class Solution {
public:
    int maximalSquare(vector<vector<char>>& matrix) {
        if (matrix.empty() || matrix[0].empty())
            return 0;

        auto row = matrix.size();
        auto col = matrix[0].size();
        vector<vector<int> > dp(row, vector<int>(col, 0));

        int res = 0;
        for (int i = 0; i < row; i++) {
            dp[i][0] = matrix[i][0] - '0';
            res = max(res, dp[i][0]);
        }

        for (int j = 0; j < col; j++) {
            dp[0][j] = matrix[0][j] - '0';
            res = max(res, dp[0][j]);
        }

        for (int i=1; i<row; i++)
            for (int j = 1; j < col; j++) {
                if (matrix[i][j] == '0') dp[i][j] = 0;
                else {
                    dp[i][j] = min({dp[i-1][j], dp[i][j-1], dp[i-1][j-1]}) + 1;
                    res = max(res, dp[i][j]);
                }
            }
        return res * res;
    }
};

13. leetcode10-正则表达式匹配

题目描述

给你一个字符串 s 和一个字符规律 p，请你来实现一个支持 '.' 和 '' 的正则表达式匹配。'.' 匹配任意单个字符'' 匹配零个或多个前面的那一个元素所谓匹配，是要涵盖整个字符串 s的，而不是部分字符串。
说明:s 可能为空，且只包含从 a-z 的小写字母。p 可能为空，且只包含从 a-z 的小写字母，以及字符 . 和 *。

输入: s = "aa" ， p = "a"
输出: false
解释: "a" 无法匹配 "aa" 整个字符串。

DP求解

DP定义：dp[i][j]: s[:i]和p[:j]是否匹配
DP初始：dp[0][0] = 1
DP转移:
写起来麻烦，看代码把！

class Solution {
public:
    bool isMatch(string s, string p) {
        vector<vector<int>> dp(s.size()+1, vector<int>(p.size()+1, 0));
        dp[0][0]=1;
        for(int i=0;i<=s.size();i++){
            for(int j=1;j<=p.size();j++){
                if(i&&(s[i-1]==p[j-1]||p[j-1]=='.')) dp[i][j] = dp[i-1][j-1];
                else if(p[j-1]=='*'&&j!=1){
                    if(i==0) dp[i][j] = dp[i][j-2];
                    else if(s[i-1]==p[j-2]||p[j-2]=='.') dp[i][j] = max(dp[i][j-2], dp[i-1][j]);
                    else dp[i][j] = dp[i][j-2];
                }
            }
        }
        return dp[s.size()][p.size()];
    }
};

动态规划

题目描述

1.1 二维DP

1.2 一维DP

题目描述

一维DP

题目描述

DP求解

题目描述

DP求解

题目描述

DP求解

题目描述

DP求解

题目描述

DP求解

题目描述

DP求解

题目描述

DP求解

题目描述

DP求解

题目描述

DP求解

题目描述

DP求解

题目描述

DP求解