动态规划五部曲

  1. 确定dp数组（dp table）以及下标的含义
  2. 确定递推公式
  3. dp数组如何初始化
  4. 确定遍历顺序
  5. 举例推导dp数组

先确定递推公式再确定如何对dp数组初始化

一维动态规划

斐波那契数列

image-20220111105547721

image-20220111105602653

  • 时间复杂度：O(n)。
  • 空间复杂度：O(1)。
1
2
3
4
5
6
7
8
9
10
11
class Solution {
public:
    int fib(int n) {
        int res[3];
        res[0] = 0;res[1] = 1;res[2] = 0;
        for(int i = 2;i <= n;i++){
            res[i%3] = (res[(i-1)%3] + res[(i-2)%3])%1000000007;
        }
        return res[n%3];
    }
};

image-20220111105656207

image-20220111105720652

上台阶问题本质也是斐波那契数列只不过更改了初始值而已。

1
2
3
4
5
6
7
8
9
10
11
class Solution {
public:
    int numWays(int n) {
        int res[3];
        res[0] = 1;res[1] = 1;
        for(int i = 2;i <= n;i++){
            res[i%3] = (res[(i-1)%3] + res[(i-2)%3])%1000000007;
        }
        return res[n%3];
    }
};

打家劫舍

image-20220111111040590

定义一个数组 dp， dp[i] 表示抢劫到第 i 个房子时，可以抢劫的最大数量。我们考虑 dp[i]，此时可以抢劫的最大数量有两种可能，一种是我们选择不抢劫这个房子，此时累计的金额即为dp[i-1]；另一种是我们选择抢劫这个房子，那么此前累计的最大金额只能是 dp[i-2]，因为我们不能够抢劫第 i-1 个房子，否则会触发警报机关。因此本题的状态转移方程为 dp[i] = max(dp[i-1],nums[i-1] + dp[i-2])。

另外注意值得初始化，dp[0]=nums[0]; dp[1]=max(nums[0],nums[1]);

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public:
    int rob(vector<int>& nums) {
        int size = nums.size();
        vector<int>dp(size,0);
        dp[0] = nums[0];
        if(size == 1)return dp[0];
        else dp[1] = max(nums[0],nums[1]);
        for(int i =2;i < size;i++){
            dp[i] = max(dp[i - 1],dp[i - 2]+nums[i]);
        }
        return dp[size - 1];
    }
};

等差数列划分

image-20220111115921990

这道题略微特殊，因为要求是等差数列，可以很自然的想到子数组必定满足 num[i] - num[i-1]= num[i-1] - num[i-2]。然而由于我们对于 dp 数组的定义通常为以 i 结尾的，满足某些条件的子数组数量，而等差子数组可以在任意一个位置终结，因此此题在最后需要对 dp 数组求和。

开始我没想到dp数组求和，结果写了一个比较复杂的方法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
class Solution {
public:
    int lenArith = 1;
    int numberOfArithmeticSlices(vector<int>& nums) {
        int len = nums.size();
        if(len <= 2)return 0;
        vector<int>dp(len,0);
        for(int i = 2;i < len;i++){
            if(isArithmetic(nums, i)){
                dp[i] = dp[i - 1] + lenArith++;
            }
            else{
                dp[i] = dp[i - 1];
                lenArith = 1;
            }
        }
        int max = -1;
        for(int i = 0;i < len;i++){
            if(max < dp[i])max =dp[i];
        }
        return max;
    }
    bool isArithmetic(vector<int>&nums,int i){
        if(nums[i]+nums[i-2]==2*nums[i-1]){
            return true;
        }
        else return false;
    }
};

其实还可以这样，简单易懂

1
2
3
4
5
6
7
8
9
10
11
int numberOfArithmeticSlices(vector<int>& nums) {
    int n = nums.size();
    if (n < 3) return 0;
    vector<int> dp(n, 0);
    for (int i = 2; i < n; ++i) {
    	if (nums[i] - nums[i-1] == nums[i-1] - nums[i-2]) {
    		dp[i] = dp[i-1] + 1;
    	}
    }
    return accumulate(dp.begin(), dp.end(), 0);
}

连续子数组的最大和

image-20220113205920320

image-20220113210057555

image-20220113210146597

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        int size = nums.size();
        vector<int>dp(size + 1,0);
        int maxn = -100;
        for(int i = 0;i < size;i++){
            dp[i+1] = max(dp[i] + nums[i],0 + nums[i]); 
            maxn = max(maxn,dp[i+1]);
        }
        return maxn;
    }
};

n个骰子的点数

image-20220223194950132

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
    vector<double> dicesProbability(int n) {
        vector<double>dp(6,1.0/6.0);

        for(int i = 2;i <= n;i++){
            vector<double>tmp(6 * i - i + 1);
            for(int k = 0;k < 6;k++){
                for(int j = 0;j < dp.size();j++){
                    tmp[k+j] += dp[j] * 1.0 /6.0;
                }            
            }
            dp = tmp;
        }
        return dp;

    }
};

338. 比特位计数

给你一个整数 n ，对于 0 <= i <= n 中的每个 i ，计算其二进制表示中 1 的个数 ，返回一个长度为 n + 1 的数组 ans 作为答案。

示例 1：

1
2
3
4
5
6
输入：n = 2
输出：[0,1,1]
解释：
0 --> 0
1 --> 1
2 --> 10

示例 2：

1
2
3
4
5
6
7
8
9
输入：n = 5
输出：[0,1,1,2,1,2]
解释：
0 --> 0
1 --> 1
2 --> 10
3 --> 11
4 --> 100
5 --> 101

二维动态规划

最小路径和

image-20220113145121206

我们可以定义一个同样是二维的 dp 数组，其中 dp[i][j] 表示从左上角开始到 (i, j) 位置的最优路径的数字和。因为每次只能向下或者向右移动，我们可以很容易得到状态转移方程 dp[i][j] =min(dp[i-1][j], dp[i][j-1]) + grid[i][j]，其中 grid 表示原数组。

这道题稍微注意一下初始化，不是很难。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
    int minPathSum(vector<vector<int>>& grid) {
        int m = mat.size(),n = mat[0].size();
        vector<vector<int>>dp(m,vector<int>(n,0));
        
        for(int i = 1;i < n;i++)dp[0][i] = dp[0][i-1] + grid[0][i];
        for(int i = 1;i < m;i++)dp[i][0] = dp[i-1][0] + grid[i][0];
        for(int i = 1;i < m;i++)
            for(int j = 1;j < n;j++){
                dp[i][j] = min(dp[i-1][j]+grid[i][j],dp[i][j-1]+grid[i][j]);
            }
        return dp[m-1][n-1];
    }
};
  • 时间复杂度：O(mn)，其中 m 和 n 分别是网格的行数和列数。需要对整个网格遍历一次，计算 \textit{dp}dp 的每个元素的值。
  • 空间复杂度：O(mn)，其中 m和 n分别是网格的行数和列数。创建一个二维数组dp，和网格大小相同。
    空间复杂度可以优化，例如每次只存储上一行的 dp 值，则可以将空间复杂度优化到 O(n)。

因为 dp 矩阵的每一个值只和左边和上面的值相关，我们可以使用空间压缩将 dp 数组压缩为一维。对于第 i 行，在遍历到第 j 列的时候，因为第 j-1 列已经更新过了，所以 dp[j-1] 代表 dp[i][j-1]的值（即为图中dp[j-1]）；而 dp[j] 待更新，当前存储的值是在第 i-1 行的时候计算的，所以代表 dp[i-1][j] 的值（即为图中dp[j]old）。

image-20220113150903937

这里写代码的时候把dp初始化为n+1个空间的数组，主要为了防止计算过程中数组越界，dp[j-1]越界。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public:
    int minPathSum(vector<vector<int>>& grid) {
        int m = grid.size();
        int n = grid[0].size();
        vector<int> dp(n+1,INT_MAX);
        dp[1] = 0;
        for(int i=1;i<=m;i++)
            for(int j=1;j<=n;j++){
                dp[j] = min(dp[j-1],dp[j])+grid[i-1][j-1];
            }
        return dp[n];
    }
};

01矩阵

image-20220113172220506

一般来说，因为这道题涉及到四个方向上的最近搜索，所以很多人的第一反应可能会是广度优先搜索。但是对于一个大小 O(mn)的二维数组，对每个位置进行四向搜索，最坏情况的时间复杂度（即全是 1）会达到恐怖的 O(m^2*n^2)。一种办法是使用一个 dp 数组做 memoization，使得广度优先搜索不会重复遍历相同位置；另一种更简单的方法是，我们从左上到右下进行一次动态搜索，再从右下到左上进行一次动态搜索。两次动态搜索即可完成四个方向上的查找。 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class Solution {
public:
    vector<vector<int>> updateMatrix(vector<vector<int>>& mat) {
        int m = mat.size(),n = mat[0].size();
        vector<vector<int>>dp(m,vector<int>(n,INT_MAX-1));

        for(int i = 0;i < m;i++)
            for(int j = 0;j < n;j++){
                if(mat[i][j] == 0){
                    dp[i][j] = 0;                    
                }
                else {
                    if(i>0)dp[i][j] = min(dp[i-1][j]+1,dp[i][j]);
                    if(j>0)dp[i][j] = min(dp[i][j-1]+1,dp[i][j]);
                }
            }
        
        for(int i = m - 1;i >= 0;i--)
            for(int j = n - 1;j >= 0;j--){ 
                if(mat[i][j]!=0) {
                    if(i<m-1)dp[i][j] = min(dp[i+1][j]+1,dp[i][j]);
                    if(j<n-1)dp[i][j] = min(dp[i][j+1]+1,dp[i][j]);
                }
            }

        return dp;    
    }
};

复杂度分析

  • 时间复杂度：O(mn)O(r**c)，其中 m 为矩阵行数，n为矩阵列数。计算 dp 数组的过程中我们需要遍历2次矩阵，因此时间复杂度为 O(2rc)=O(rc)。
  • 空间复杂度：O(1)，这里我们只计算额外的空间复杂度。除了答案数组以外，我们只需要常数空间存放若干变量。

最大正方形

image-20220113175114682

对于在矩阵内搜索正方形或长方形的题型，一种常见的做法是定义一个二维 dp 数组，其中dp[i][j] 表示满足题目条件的、以 (i, j) 为右下角的正方形或者长方形的属性。对于本题，则表示以 (i, j) 为右下角的全由 1 构成的最大正方形面积。如果当前位置是 0，那么 dp[i][j] 即为 0；如果当前位置是 1，我们假设 dp[i][j] = k2，其充分条件为 dp[i-1][j-1]、 dp[i][j-1] 和 dp[i-1][j] 的值必须都不小于 (k - 1)^2，否则 (i, j) 位置不可以构成一个边长为 k 的正方形。同理，如果这三个值中的的最小值为 k - 1，则 (i, j) 位置一定且最大可以构成一个边长为 k 的正方形。

image-20220113175557568 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
    int maximalSquare(vector<vector<char>>& matrix) {
        int m = matrix.size(),n = matrix[0].size();
        vector<vector<int>>dp(m,vector<int>(n,0));
        int maxm = 0;

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

编辑距离

image-20220222201813891

image-20220222202017118

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public:
    int minDistance(string word1, string word2) {
        int m = word1.size(),n = word2.size();
        vector<vector<int>>dp(m+1,vector<int>(n+1,0));
        for(int i = 1;i < m + 1;i++){
            dp[i][0] = dp[i-1][0] + 1;
        }
        for(int i = 1;i < n + 1;i++){
            dp[0][i] = dp[0][i-1] + 1;
        }
        
        for(int i = 1;i < m + 1;i++){
            for(int j = 1;j < n + 1;j++){
                if(word1[i - 1] == word2[j - 1])dp[i][j] = dp[i-1][j-1];
                else dp[i][j] = min(dp[i][j-1],min(dp[i-1][j],dp[i-1][j-1])) + 1;
            }
        }
        return dp[m][n];

    }
};

分割类问题

该数的完全平方数个数

image-20220113180553712

对于分割类型题，动态规划的状态转移方程通常并不依赖相邻的位置，而是依赖于满足分割条件的位置。我们定义一个一维矩阵 dp，其中 dp[i] 表示数字 i 最少可以由几个完全平方数相加构成。在本题中，位置 i 只依赖 i - k^2 的位置，如 i - 1、 i - 4、 i - 9 等等，才能满足完全平方分割的条件。因此 dp[i] 可以取的最小值即为 1 + min(dp[i-1], dp[i-4], dp[i-9] · · · )。 

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
public:
    int numSquares(int n) {
        vector<int>dp(n+1,INT_MAX);
        dp[0] = 0;
        for(int i = 1;i < n+1;i++)
            for(int j = 1;j*j <= i;j++)
                dp[i] = min(dp[i - j*j] + 1,dp[i]);

        return dp[n];
    }
};

image-20220113180712089

解码方法总数

image-20220113183610625

这个题目难在对情况的各个分类，想清楚了还是好做的。

首先按道理来说译码只应有一种，dp[i] = dp[i-1],但是由于0，1，2存在多了各种可能，就逐条分情况

image-20220113183754865

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
    int numDecodings(string s) {
        if (s[0] == '0') return 0;
        vector<int> dp(s.size()+1);
        dp[0]=1;dp[1]=1;
        for (int i =1; i < s.size(); i++) {
            if (s[i] == '0')//1.s[i]为0的情况
                if (s[i - 1] == '1' || s[i - 1] == '2') //s[i - 1]等于1或2的情况
                    dp[i+1] = dp[i-1];//由于s[1]指第二个下标，对应为dp[2],所以dp的下标要比s大1，故为dp[i+1]
                else 
                    return 0;
            else //2.s[i]不为0的情况
                if (s[i - 1] == '1' || (s[i - 1] == '2' && s[i] <= '6'))//s[i-1]s[i]两位数要小于26的情况
                    dp[i+1] = dp[i]+dp[i-1];
                else//其他情况
                    dp[i+1] = dp[i];
        }
        return dp[s.size()];
    }
};       
1
2
3
4
5
6
7
8
9
10
11
12
13
14
int numDecodings(string s) {
    if (s[0] == '0') return 0;
    int pre = 1, curr = 1;//dp[-1] = dp[0] = 1
    for (int i = 1; i < s.size(); i++) {
        int tmp = curr;
        if (s[i] == '0')
            if (s[i - 1] == '1' || s[i - 1] == '2') curr = pre;
            else return 0;
        else if (s[i - 1] == '1' || (s[i - 1] == '2' && s[i] >= '1' && s[i] <= '6'))
            curr = curr + pre;
        pre = tmp;
    }
    return curr;
}

image-20220113185733117

单词拆分

image-20220113203539736

类似于完全平方数分割问题，这道题的分割条件由集合内的字符串决定，因此在考虑每个分割位置时，需要遍历字符串集合，以确定当前位置是否可以成功分割。注意对于位置 0，需要初始化值为真。 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
    bool wordBreak(string s, vector<string>& wordDict) {
        int len = s.length();
        vector<bool>dp(len+1,false);
        dp[0] = true;
        for(int i = 1;i < len+1;i++){
            for (auto word : wordDict){
                int l = word.length();
                if(i >= l&&s.substr(i - l, l)==word){
                    dp[i] = dp[i - l] || dp[i];// ||dp[i]保证成功分割后true不会受其他字符串影响而变为false
                }
            }
        }
        return dp[len];
    }
};

子序列问题

最长递增子序列

image-20220114125312402

在本题中， dp[i] 可以表示以 i 结尾的、最长子序列长度。对于每一个位置 i，如果其之前的某个位置 j 所对应的数字小于位置 i 所对应的数字，则我们可以获得一个以 i 结尾的、长度为 dp[j]+ 1 的子序列。为了遍历所有情况，我们需要 i 和 j 进行两层循环，其时间复杂度为 O(n^2)。 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
    int lengthOfLIS(vector<int>& nums) {
        int n = nums.size();
        vector<int>dp(n,1);
        int maxm = 0;
        for(int i = 0;i < n;i++){
            for(int j = 0;j < i;j++){
                if(nums[j] < nums[i]){
                    dp[i] = max(dp[i],dp[j]+1);
                }
            }
            maxm = max(dp[i],maxm);
        }
        return maxm;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
using namespace std;
struct Node {
    int x;
    int y;

};
bool cmp(Node& a, Node& b) {
    if (a.x == b.x)return a.y > b.y;
    return a.x < b.x;
}
void func() {
    int n; cin >> n;
    vector<Node>nodes(n+1, Node{ 0,0 });
    for (int i = 1; i <= n; i++) {
        cin >> nodes[i].x;
    }
    for (int i = 1; i <= n; i++) {
        cin >> nodes[i].y;
    }

    sort(nodes.begin()+1, nodes.end(), cmp);

    int sum = 0;
    vector<int>tails(n + 1, -1);
    int end = 0;
    for (int i = 1; i <= n; i++) {
        if (tails[end] < nodes[i].y) {
            end++;
            tails[end] = nodes[i].y;
        }
        else {
            int l = 0; int r = end;
            while (l + 1 != r) {
                int mid = l + ((r - l) >> 1);
                if (tails[mid] >= nodes[i].y) {
                    r = mid;
                }
                else l = mid;
            }
            tails[r] = nodes[i].y;
        }
    }
    cout << end << endl;
}
int main()
{
    int T;
    cin >> T;
    for (int j = 0; j < T; j++) {
        func();
    }


    return 0;
}

最长公共子序列

image-20220114133601443

对于子序列问题，第二种动态规划方法是，定义一个 dp 数组，其中 dp[i] 表示到位置 i 为止的子序列的性质，并不必须以 i 结尾。这样 dp 数组的最后一位结果即为题目所求，不需要再对每个位置进行统计。
在本题中，我们可以建立一个二维数组 dp，其中 dp[i][j] 表示到第一个字符串位置 i 为止、到第二个字符串位置 j 为止、最长的公共子序列长度。这样一来我们就可以很方便地分情况讨论这两个位置对应的字母相同与不同的情况了

从初值开始考虑dp[i][0]这一列设为0，dp[0][j]这一列设为0，因为一个字符串前0个字符和另一个字符串公共长度一定是0
而后考虑dp[i][j]与dp[i-1][j],dp[i][j-1],dp[i-1][j-1]这三个的关系。
首先最容易确定的是dp[i][j] = dp[i-1][j-1] + 1;这代表着text1[i]与text2[j]两个字符串新加上的末尾字符相等，那么一定是等于dp[i-1][j-1]+1。
对于text1[i]与text2[j]两个字符串的末尾字符不相等的情况，那么从根来推： 当前两个字符不等，text1[i]!=text2[j]的话，那么长度最少也是dp[i-1][j-1]，但这还不够，因为我们希望拿到之前的比较中尽可能大的长度。那么当前字符已经不相等的情况下，就应该把当前的字符也放入到之前的比较中，那么一定有dp[i][j-1]和dp[i-1][j]>=dp[i][j]。简单来说，dp[i][j]的值应该从dp[i-1][j-1],dp[i][j-1],dp[i-1][j]三者中取，但dp[i][j]≤另外两个，故比较另外两个，取较大的。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
    int longestCommonSubsequence(string text1, string text2) {
        int m = text1.length(), n = text2.length();
        vector<vector<int>> dp(m + 1, vector<int>(n + 1, 0));
aacx
aaxc
        for(int i = 1;i < m+1;i++){
            for(int j = 1;j < n+1;j++){
                if(text1[i-1] == text2[j-1]){
                    dp[i][j] = dp[i-1][j-1] + 1;
                }
                else{
                    dp[i][j] = max(dp[i][j-1],dp[i-1][j]);
                }
            }
        }
        return dp[m][n];
    }
};

n个物品递增阿里笔试

背包问题

0/1背包

我们可以用动态规划来解决背包问题。以 0-1 背包问题为例。我们可以定义一个二维数组 dp存储最大价值，其中 dp[i][j] 表示前 i 件物品体积不超过 j 的情况下能达到的最大价值。在我们遍历到第 i 件物品时，在当前背包总容量为 j 的情况下，如果我们不将物品 i 放入背包，那么 dp[i][j]= dp[i-1][j]，即前 i 个物品的最大价值等于只取前 i-1 个物品时的最大价值；如果我们将物品 i 放入背包，假设第 i 件物品体积为 w，价值为 v，那么我们得到 dp[i][j] = dp[i-1][j-w] + v。我们只需在遍历过程中对这两种情况取最大值即可，总时间复杂度和空间复杂度都为 O(NW)。

image-20220225204655906

image-20220225212401666

image-20220225204159873

核心代码

1
2
3
4
5
6
7
8
for (int i = 1; i <= n; i++) {
    for (int j = 1; j <= m; j++) {
        if (j < w[i])
            dp[i][j] = dp[i - 1][j];
        else
            dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - w[i]] + c[i]);
    }
}

我们可以进一步对 0-1 背包进行空间优化，将空间复杂度降低为 O(W)。如图所示，假设我们目前考虑物品 i = 2，且其体积为 w = 2，价值为 v = 3；对于背包容量 j，我们可以得到 dp[2][j]= max(dp[1][j], dp[1][j-2] + 3)。这里可以发现我们永远只依赖于上一排 i = 1 的信息，之前算过的其他物品都不需要再使用。因此我们可以去掉 dp 矩阵的第一个维度，在考虑物品 i 时变成 dp[j]= max(dp[j], dp[j-w] + v)。这里要注意我们在遍历每一行的时候必须逆向遍历，这样才能够调用上一行物品 i-1 时 dp[j-w] 的值；若按照从左往右的顺序进行正向遍历，则 dp[j-w] 的值在遍历到j 之前就已经被更新成物品 i 的值了 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
    for (int i = 1; i <= n; i++) {
        for (int j = m; j >= 1; j--) {//注意这里是逆向遍历！！！
            if (j < w[i])
                dp[j] = dp[j];
            else
                dp[j] = max(dp[j], dp[j - w[i]] + c[i]);
        }
    }

//继续小小优化，删去一个if分支
    for (int i = 1; i <= n; i++) {
        for (int j = m; j >= 1; j--) {//注意这里是逆向遍历！！！
            if (j >= w[i])
                dp[j] = max(dp[j], dp[j - w[i]] + c[i]);
        }
    }

完全背包

image-20220225205927557

一个朴素的想法，在完全背包问题中，一个物品可以拿多次。我们就选择一直拿到放不下为止，如图上半部分所示，假设我们遍历到物品 i = 2，且其体积为 w = 2，价值为 v = 3；对于背包容量 j = 5，最多只能装下 2 个该物品。那么我们的状态转移方程就变成了 dp[2][5] = max(dp[1][5], dp[1][3] + 3, dp[1][1] + 6)。

image-20220225210209915

只需在0/1背包基础上稍作修改

1
2
3
4
5
6
7
8
for (int i = 1; i <= n; i++) {
    for (int j = m; j >= 1; j--) {//注意这里是逆向遍历！！！
        for(int k = 0;k <= j/w[i];k++){
            if (j >= w[i])
            	dp[j] = max(dp[j], dp[j - k * w[i]] + k * c[i]);
        }		
    }
}

但是如果采用这种方法，假设背包容量无穷大而物体的体积无穷小，我们这里的比较次数也会趋近于无穷大，远超 O(NW)的时间复杂度

image-20220225212420539

1
2
3
4
5
6
7
8
9
10
11
12
for (int i = 1; i <= n; i++) {
    for (int j = 0; j <= m; j++) {//注意这里是顺向遍历！！！
            if (j >= w[i])
            	dp[j] = max(dp[j], dp[j - w[i]] + c[i]);	
    }
}

for (int i = 1; i <= n; i++) {
    for (int j = w[i]; j <= m; j++) {//注意这里是顺向遍历！！！
    	dp[j] = max(dp[j], dp[j - w[i]] + c[i]);	
    }
}

分割等和子集

image-20220225215845205

image-20220225215835338

思路分析：

0/1背包问题，区别在于
原先的0/1背包大小是给你一个值m，总体积不超过m即可。
这一题稍作变换，体积要求，给你一个值m，值m应该为数组和的一半，总体积要恰好等于m。物品数量即数组大小。
初始化分析dp[0][0]意为0件物品总和体积为0，这个值必然为true。
我们最终目标是求得dp[num.size][sum/2]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
    bool canPartition(vector<int>& nums) {
        int n = nums.size();
        int sum = accumulate(nums.begin(),nums.end(),0);
        if(sum%2)return false;
        else sum /= 2;
        
        //注意sum已经除以了2，即 nums总和/2
        vector<bool>dp(sum+1,false);
        for(int i = 0; i <= n;i++)dp[0] = true;
        
        for(int i = 1;i <= n;i++){
            for(int j = sum;j >= nums[i-1];j--){
                dp[j] = dp[j] || dp[j-nums[i-1]];
            }
        }        
        return dp[sum];
    }
};

一和零

image-20220226185023400

思路分析：

0/1背包问题，区别在于
原先的0/1背包大小是给你一个值m，总体积不超过m即可。
而这一题稍作变换，有两个体积要求，字符’0’的总体积（数量）不超过m，字符’1’的总体积（数量）不超过n。而每件物品的价值均是字符’0’的数量和字符’1’的数量。物品数量即总共的字符串数量。

1
2
3
4
5
6
7
8
for(int i = 1;i <= size;i++)//物品数量
    for(int j = m;j >= w[i];j--)
        dp[j] = max(dp[j],dp[j - w[i]]);
//稍作修改...
for(int i = 1;i <= size;i++)//物品数量
    for(int j = m;j >= nums0(物品i);j--)
        for(int k = n;k >= nums1(物品i);k--)
        	dp[j] = max(dp[j][k],dp[j - nums0(物品i)][k - nums1(物品i)]);
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
class Solution {
public:
    int findMaxForm(vector<string>& strs, int m, int n) {
        int size = strs.size();
        vector<vector<int>>dp(m + 1,vector<int>(n + 1,0));
        for(int i = 1; i <= size;i++){
            
            int nums0 = nums_0(strs[i-1]);
            int nums1 = nums_1(strs[i-1]);
            
            for(int j = m;j >= nums0;j--){
                for(int k = n;k >= nums1;k--){
                    
                    if(j >= nums0 && k >= nums1)
                        dp[j][k] = max(dp[j][k],dp[j-nums0][k-nums1] + 1);
                                     
                }
            }
        }
        return dp[m][n];
    }

    int nums_1(string str){
        int a = 0;
        for(int i = 0;i < str.length();i++){
            if(str[i] == '1')a++;
        }
        return a;
    }
    int nums_0(string str){
        int a = 0;
        for(int i = 0;i < str.length();i++){
            if(str[i] == '0')a++;
        }
        return a;
    }
};

494. 目标和

image-20220420112226875

方法一：回溯

时间复杂度过高

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
    int targetSum;
    int results = 0; 
public:
    int findTargetSumWays(vector<int>& nums, int target) {
        targetSum = target;
        dfs(nums,0,0);
        return results;
    }
    void dfs(vector<int>&nums,int cur,int sum){
        if(cur == nums.size() && sum == targetSum){
            results++;
        }
        else if(cur == nums.size()){
            return;
        }
        else{
            dfs(nums,cur + 1,sum + nums[cur]);
            dfs(nums,cur + 1,sum - nums[cur]);
        }
    }
};

方法二：动态规划

  1. 确定dp数组（dp table）以及下标的含义
  2. 确定递推公式
  3. dp数组如何初始化
  4. 确定遍历顺序
  5. 举例推导dp数组

1.确定dp数组（dp table）以及下标的含义
搞清楚需要输出的结果后，就可以来想办法画一个表格，也就是定义dp数组的含义。根据背包问题的经验，可以将dp[ i ][ j ]定义为从数组nums中 0 - i 的元素进行加减可以得到 j 的方法数量。

image-20220420112551981

2.确定递推公式
搞清楚状态以后，我们就可以根据状态去考虑如何根据子问题的转移从而得到整体的解。这道题的关键不是nums[i]的选与不选，而是nums[i]是加还是减，那么我们就可以将方程定义为：

dp[ i ][ j ] = dp[ i - 1 ][ j - nums[ i ] ] + dp[ i - 1 ][ j + nums[ i ] ]
可以理解为nums[i]这个元素我可以执行加，还可以执行减，那么我dp[i][j]的结果值就是加/减之后对应位置的和。

3.dp数组如何初始化
这个数组第一行应该要有初始化状态，初始化应该就是
dp[0][sum + nums[0]]++; 与 dp[0][sum - nums[0]]++;

4.确定遍历顺序
二维数组简单点，从左到右，从上到下

5.举例推导dp数组

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
public:
    int findTargetSumWays(vector<int>& nums, int target) {
        //dp[i][j] 前i-1个数进行加减操作可以得到的结果为j的方法总数
        int len = nums.size();
        int sum = accumulate(nums.begin(),nums.end(),0);
        if(abs(sum) < abs(target) || (sum + target)%2 == 1)return 0;
        vector<vector<int>>dp(len,vector<int>(2 * sum + 1,0));
        
        dp[0][sum + nums[0]]++;
        dp[0][sum - nums[0]]++;

        for(int i = 1;i < len;i++){
            for(int j = 0;j <= sum * 2;j++){
                int l1 = 0,l2 = 0;
                if(j - nums[i] >= 0 && j - nums[i] <= 2 * sum)l1 = dp[i-1][j-nums[i]];
                if(j + nums[i] >= 0 && j + nums[i] <= 2 * sum)l2 = dp[i-1][j+nums[i]]; 
                
                dp[i][j] = l1 + l2;
            }
        }
        return dp[len-1][sum + target];
    }
};

股票交易问题

股票最大利润

image-20220123204355013

许久没做了竟然忘了？？？开始思路还是还是暴力求解

1
2
3
4
5
6
7
8
9
10
int maxProfit(vector<int>& prices) {
    int size = prices.size();
    int maxp = 0;
    for(int i = 0;i < size;i++){
        for(int j = i + 1;j < size;j++){
            maxp = max(prices[j] - prices[i],maxp);
        }
    }
    return maxp;
}

这样时间复杂度O(n^2)，但是明显可以压缩，此题可以定义一个状态转移方程dp[i] = max(dp[i-1] , prices[i] - min(prince[0 : i]));
而求取min值的时候也可以简便一下，minp = min(minp,prices[i])，而不是重新再遍历一遍。同样的dp数组可以继续缩减为O(1)，只需两个变量存储无需dp数组。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int size = prices.size();
        if(size == 0)return 0;
        int dpi = 0,dpi_1 = 0;
        int minp = prices[0];
        for(int i = 1;i < size;i++){     
            dpi = max(dpi_1,prices[i] - minp);
            minp = min(minp,prices[i]);
            dpi_1 = dpi;
        }
        return dpi;
    }
};

股票问题系列通解

因此对T[i][k]的定义需要分成两项：

T[i][k][0] 表示在第 i 天结束时，最多进行 k 次交易且在进行操作后持有 0 份股票的情况下可以获得的最大收益；
T[i][k][1] 表示在第 i 天结束时，最多进行 k 次交易且在进行操作后持有 1 份股票的情况下可以获得的最大收益。
使用新的状态表示之后，可以得到基准情况和状态转移方程。

基准情况：

1
2
T[-1][k][0] = 0, T[-1][k][1] = -Infinity
T[i][0][0] = 0, T[i][0][1] = -Infinity

状态转移方程：

1
2
T[i][k][0] = max(T[i - 1][k][0], T[i - 1][k][1] + prices[i])
T[i][k][1] = max(T[i - 1][k][1], T[i - 1][k - 1][0] - prices[i])
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
#include <iostream>
#include <vector>

using namespace std;

int main() {
    int N = 0;
    cin >> N;
    vector<vector<int>>arr(N,vector<int>(N,0));
    int des = 0;
    int i = 0,j = 0;
    for(int k = 0;k < N*N;){       

        if(des%4 == 0&&j < N&&arr[i][j] == 0)arr[i][j++] = ++k;
        else if(des%4 == 1&&i < N&&arr[i][j] == 0)arr[i++][j] = ++k;
        else if(des%4 == 2&&j >= 0&&arr[i][j] == 0)arr[i][j--] = ++k;
        else if(des%4 == 3&&i >= 0&&arr[i][j] == 0)arr[i--][j] = ++k;
        else {
            if(des%4 == 0)j--;
            else if (des%4 == 1)i--;
            else if(des%4 == 2)j++;
            else if(des%4 == 3)i++; 
            des++;continue;
        }

        if(i == N/2&& j==N/2)break;
    }    
    for(int i = 0;i < N;i++){
        for(int j = 0;j < N;j++){
            cout << arr[i][j] <<" ";
        }
        cout << endl;
    }
    return 0;
}

字符串问题

image-20220320181102941

image-20220320181308039

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public:
    int translateNum(int num) {
        string s = to_string(num);
        vector<unsigned int>dp(s.size()+1,0);
        dp[0] = 1;
        dp[1] = 1;
        for(int i = 2;i <= s.size();i++){
            if(s[i-2]=='1' || (s[i-2]=='2'&&s[i-1]<='5'))dp[i] = dp[i-1]+dp[i-2];
            else dp[i] = dp[i-1];
        }
        return dp[s.size()];
    }
};

回文字符串

5. 最长回文子串

image-20220422120115579

  1. 确定dp数组以及下标的含义
  • dp[i][j]：表示区间范围[i,j]的子串是否是回文子串，如果是dp[i][j]为true，否则为false。
  1. 状态转移方程
    回文串的定义是正反读都是一样说明，回文串的首尾字符肯定一样所以秉持这个定义进行分类讨论：

  • 当s[i]与s[j]不相等，肯定不是回文子串即dp[i][j]= false。

  • 当s[i]与s[j]相等时，需要判断 i 和 j 的情况

    1. i = j ：说明在区间内只有一个字符所以是回文子串即 dp[i][j] = true

    2. i-j = 1：说明在区间内有两个相等的字符所以是回文子串即 dp[i][j] = true

    3. i-j > 1：说明区间内字符数已经大于等于三个所以要判断此区间内是不是字符串需要将区间缩小即要判断[i+1,j-1]区间是否是回文串。若是则dp[i][j] = true；
      最后就是当是回文串的时候记录最大长度和更新起始位置（和上题多了这个判断）
      以上三种情况分析完了，那么递归公式如下：

      1
      2
      3
      4
      5
      6
      if(s[i] == s[j] && j - i <= 1){
          dp[i][j] = true;
      }
      else if(s[i] == s[j] && dp[i+1][j-1] == true){
          dp[i][j] = true;
      }

  1. dp数组初始化
    dp[i][j]初始化为false

  2. 确定遍历顺序
    由情况3可知dp[i][j]的状态是由dp[i + 1][j - 1]所以i是有i+1推得，j由j-1推得所以综上分析i应该从大到小倒序，j应该从i开始正序遍历 ，保证了dp[i + 1][j - 1]都是经过计算的

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
string longestPalindrome(string s) {
    int len = s.length();
    int maxl = 0;
    int l = 0,r = 0;
    vector<vector<bool>>dp(len,vector<bool>(len,false));

    for(int i = len-1;i >= 0;i--){
        for(int j = i;j < len;j++){
            if(s[i] == s[j] && j - i <= 1){
                dp[i][j] = true;
            }
            else if(s[i] == s[j] && dp[i+1][j-1] == true){
                dp[i][j] = true;
            }

            if(dp[i][j] && j - i > maxl){
                maxl = j - i;
                l = i;
                r = j;
            }
        }
    }
    return s.substr(l,r-l+1);
}

647. 回文子串

image-20220422120538915

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
int countSubstrings(string s) {
    int len = s.length();
    //1.dp[i][j]表示区间[i,j]是否为回文字符串
    vector<vector<bool>>dp(len,vector<bool>(len,false));
    int result = 0;
    for(int i = len-1;i >= 0;i--){
        for(int j = i;j <= len;j++){
            if(s[i] == s[j] && j - i <= 1){
                dp[i][j] = true;
                result++;
            }
            else if(s[i] == s[j] && dp[i + 1][j - 1] == true){
                dp[i][j] = true;
                result++;
            }
        }
    }
    return result;
}