LeetCode动态规划基础题-总结(超级长文)_一个人从一个房间走到另一个房间需要走n米,这个人每步可以走1米或2米,他一共有多

前言

五一留校，要不学习一下，整理了一下之前学习的动态的笔记~-
-_-…… 这部分的题目 确实很有质量的呀，认真看完，会有收获的啦。
感谢代码随想录、LeetCode 真是非常好的练习平台和习题讲解。

喜欢的同学，麻烦给个赞呗，博客书写长文不易。

一、基础的问题

1. 斐波那契

class Solution {
public:
    int fib(int N) {
        if (N <= 1) return N;
        vector<int> dp(N + 1);
        dp[0] = 0;
        dp[1] = 1;
        for (int i = 2; i <= N; i++) {
            dp[i] = dp[i - 1] + dp[i - 2];
        }
        return dp[N];
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13

2. 爬楼梯

// 版本一
class Solution {
public:
    int climbStairs(int n) {
        if (n <= 1) return n; // 因为下面直接对dp[2]操作了，防止空指针
        vector<int> dp(n + 1);
        dp[1] = 1;
        dp[2] = 2;
        for (int i = 3; i <= n; i++) { // 注意i是从3开始的
            dp[i] = dp[i - 1] + dp[i - 2];
        }
        return dp[n];
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14

3 使用最小花费爬楼梯

// 版本一
class Solution {
public:
    int minCostClimbingStairs(vector<int>& cost) {
        vector<int> dp(cost.size());
        dp[0] = cost[0];
        dp[1] = cost[1];
        for (int i = 2; i < cost.size(); i++) {
            dp[i] = min(dp[i - 1], dp[i - 2]) + cost[i];
        }
        // 注意最后一步可以理解为不用花费，所以取倒数第一步，第二步的最少值
        return min(dp[cost.size() - 1], dp[cost.size() - 2]);
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14

4 不同路径

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

5 不同路径II

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

6. 整数拆分(剪绳子)

与整数拆分的题目是一样的，

class Solution {
public:
    int cuttingRope(int n) {
        //适当地举例子才能找到规律
        // 2 =1, 3=2, 4=4=dp[4] = max(dp[4-1]*dp[1]=dp[4-2]*dp[2])
        // 因为题目说n>1 所以边界判断可以简化
        if(n <4)
            return n-1;
        vector<int> dp(n+1,0);
        dp[0] = 0;
        dp[1] = 1;
        dp[2] = 2;
        dp[3] = 3;// 表示如果长度大于4的情况下 3 dp[3]不需要切分 为3
        // dp[i] = dp[i-j]*dp[j]; dp[i]当前最大乘积
        int maxValue = 0;
        for(int i = 4; i <=n; ++i){
            for(int j = 1; j <i; ++j){
                dp[i] = dp[i -j]*dp[j];
                maxValue = max(maxValue,dp[i]);
                dp[i]  = maxValue;
            }
        }
        return dp[n];
    }
};
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

一步到位的递归：

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

• 时间复杂度：O(n^2)
• 空间复杂度：O(n)

大数版

这题已经不能用动态规划了，因为取余之后max函数不能用来比较大小了。

比如取余后2000000014 会小于 1000000020

class Solution {
private:
    const long long int mod = 1e9+7;
public:
    int cuttingRope(int n) {
        // 尽可能与更多的3相乘
        if(n <= 3) return n -1;
        long res = 1;
        while(n > 4){
            res = (res * 3) %mod;
            n -= 3;
        }
        return (res *n) %mod;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

7 不同的二叉树

96.不同的二叉搜索树

给定一个整数 n，求以 1 … n 为节点组成的二叉搜索树有多少种？

示例:

思路：

先找规律

dp[3]，就是 元素1为头结点搜索树的数量 + 元素2为头结点搜索树的数量 + 元素3为头结点搜索树的数量

元素1为头结点搜索树的数量 = 右子树有2个元素的搜索树数量 * 左子树有0个元素的搜索树数量

元素2为头结点搜索树的数量 = 右子树有1个元素的搜索树数量 * 左子树有1个元素的搜索树数量

元素3为头结点搜索树的数量 = 右子树有0个元素的搜索树数量 * 左子树有2个元素的搜索树数量

有2个元素的搜索树数量就是dp[2]。

有1个元素的搜索树数量就是dp[1]。

有0个元素的搜索树数量就是dp[0]。

所以dp[3] = dp[2] * dp[0] + dp[1] * dp[1] + dp[0] * dp[2]

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-S1SiQqex-1651670944344)(https://gitee.com/YDLinGit/blog-img/raw/master/20210107093226241.png)]

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

8 爬楼梯与升级版

class Solution {
public:
    int climbStairs(int n) {
        // 动态规划的斐波那契
        // 依然可以用记忆化搜索
        long long f1 = 1;
        long long f2 = 2;
        long long f3 = 3;
        if(n == 1) return f1;
        if(n == 2) return f2;
        for(int i = 3; i <=n; i++){
            f3 = f1 + f2;
            f1 = f2;
            f2 = f3;
        } 
        return f3;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

背包的知识：

class Solution {
public:
    int climbStairs(int n) {
        vector<int> dp(n + 1, 0);
        dp[0] = 1;
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) { // 把m换成2，就可以AC爬楼梯这道题
                if (i - j >= 0) dp[i] += dp[i - j];
            }
        }
        return dp[n];
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13

9 花费体力的爬楼梯

第一反应的解法：

其实就是第一步或者第二步不算体力的问题

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

class Solution {
public:
    int minCostClimbingStairs(vector<int>& cost) {
        vector<int> dp(cost.size()+1,0);
        if(cost.size() == 2) return min(cost[0],cost[1]);
        if(cost.size() == 3) return min(cost[1],cost[0]+cost[2]);
        // dp[i]走当前这一步，算上这一个位置后的体力消耗
        dp[0] = cost[0];
        dp[1] = cost[1];
        int n = cost.size();
        for(int i = 2; i <n; ++i){
            dp[i] = min(dp[i-1],dp[i-2]) + cost[i];
        }
        // 最后一步和最后两步去最小的一步就可以了
        return min(dp[n-1],dp[n-2]);
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

一、背包问题

理解dp[i][j]的含义：从下标为[0-i]的物品里任意取，放进容量为j的背包，价值总和。

转态转移方程：
dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]);

背包理论-滚动数组

此时dp[j]有两个选择，一个是取自己dp[j] 相当于 二维dp数组中的dp[i-1][j]，即不放物品i，一个是取dp[j - weight[i]] + value[i]，即放物品i，指定是取最大的，毕竟是求最大价值

dp[j] 容量为j的背包，所背的物品价值可以最大为dp[j]。

dp[j - weight[i]]表示容量为j - weight[i]的背包

递推公式：

dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);
1

需要注意的是一维的时候，与遍历的顺序有关，需要考虑是否覆盖

两份的代码：

注意：
dp数组下标越界的问题！

void test_2_wei_bag_pro(){
	vector<int>  weight = {1,2,4};
	vector<int> value = {15,20,30};
	int bagweight = 4;
	
	vector<vector<int>> dp(weight.size(), vector<int>(bagweight+1,0));
	
	// 初始化
	for(int i = 1; i <= bagweight; i++){
		dp[0][i] = value[0];
	} 
	
	for(int i = 1; i < weight.size(); ++i){
		for(int j = 0; j <= bagweight; ++j){
			if(j < weight[i]) dp[i][j] = dp[i -1][j];
			// 代码 
			else
				dp[i][j] = max(dp[i-1][j], dp[i-1][j - weight[i]] + value[i]);		
		}
	}
	
	cout<<dp[weight.size()-1][bagweight]; 
}	

test_1_wei_bag_problem(){
	vector<int>  weight = {1,2,4};
	vector<int> value = {15,20,30};
	int bagweight = 4;
	vector<int>dp(bagweight+1,0);
	for(int i = 0; i< weight.size(); ++i){
		for(int j = bagweight; j>=weight[i];--j){
			dp[j] = max(dp[j],dp[j-weight[i]] + value[i]);
		}
	}
	cout<<dp[bagweight];
}

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

分割等和子集

416. 分割等和子集

题目难易：中等

给定一个只包含正整数的非空数组。是否可以将这个数组分割成两个子集，使得两个子集的元素和相等。

注意: 每个数组中的元素不会超过 100 数组的大小不会超过 200

示例 1: 输入: [1, 5, 11, 5] 输出: true 解释: 数组可以分割成 [1, 5, 5] 和 [11].

示例 2: 输入: [1, 2, 3, 5] 输出: false 解释: 数组不能分割成两个元素和相等的子集.

提示：

• 1 <= nums.length <= 200
• 1 <= nums[i] <= 100

思路：

是否可以将这个数组分割成两个子集，使得两个子集的元素和相等。

那么只要找到集合里能够出现 sum / 2 的子集总和，就算是可以分割成两个相同元素和子集了。

只有确定了如下四点，才能把01背包问题套到本题上来。

• 背包的体积为sum / 2
• 背包要放入的商品（集合里的元素）重量为 元素的数值，价值也为元素的数值
• 背包如果正好装满，说明找到了总和为 sum / 2 的子集。
• 背包中每一个元素是不可重复放入。

dp[j]表示 背包总容量是j，最大可以凑成j的子集总和为dp[j]

如果dp[j] == j 说明，集合中的子集总和正好可以凑成总和j

class Solution {
public:
    bool canPartition(vector<int>& nums) {
        // 背包问题：
        // dp[j] 表示容量为j的情况下最多存储多少个
        vector<int> dp(10001,0);
        // target = sum /2; dp[target] = target是输出
        int sum = 0;
        for(int i = 0; i<nums.size(); ++i){
            sum += nums[i];
        }
        if(sum % 2 == 1) return false;
        int target = sum/2;
        // 动态规划要注意一个元素只能选取一次
        for(int i = 0; i < nums.size(); ++i){
            for(int j = target; j >= nums[i]; j--){
                dp[j] = max(dp[j], dp[j - nums[i]] + nums[i]);
            }
        }
        if(dp[target] == target) return true;
        else 
            return false;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

最后一块石头的重量

1049 最后一块石头的重量

题目难度：中等

有一堆石头，每块石头的重量都是正整数。

每一回合，从中选出任意两块石头，然后将它们一起粉碎。假设石头的重量分别为 x 和 y，且 x <= y。那么粉碎的可能结果如下：

如果 x == y，那么两块石头都会被完全粉碎； 如果 x != y，那么重量为 x 的石头将会完全粉碎，而重量为 y 的石头新重量为 y-x。 最后，最多只会剩下一块石头。返回此石头最小的可能重量。如果没有石头剩下，就返回 0。

示例： 输入：[2,7,4,1,8,1] 输出：1 解释： 组合 2 和 4，得到 2，所以数组转化为 [2,7,1,8,1]， 组合 7 和 8，得到 1，所以数组转化为 [2,1,1,1]， 组合 2 和 1，得到 1，所以数组转化为 [1,1,1]， 组合 1 和 1，得到 0，所以数组转化为 [1]，这就是最优值。

本题关键的地方就是尽量让石头分成重量相同的两堆，相撞之后剩下的石头最小。

也就是两部分，每一部分尽可能接近sum/2

递推公式还是上面那个。

在计算target的时候，target = sum / 2 因为是向下取整，所以sum - dp[target] 一定是大于等于dp[target]的

dp[j]表示容量（这里说容量更形象，其实就是重量）为j的背包，最多可以背dp[j]这么重的石头。

剩下的石头就是(sum - dp[target] - dp[target])

class Solution {
public:
    int lastStoneWeightII(vector<int>& stones) {
        vector<int> dp(15001, 0);
        int sum = 0;
        for (int i = 0; i < stones.size(); i++) sum += stones[i];
        int target = sum / 2;
        for (int i = 0; i < stones.size(); i++) { // 遍历物品
            for (int j = target; j >= stones[i]; j--) { // 遍历背包
                dp[j] = max(dp[j], dp[j - stones[i]] + stones[i]);
            }
        }
        return sum - dp[target] - dp[target];
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

目标和

493 目标和

与之前的问题不同，之前都是求容量为j的背包，最多能装多少。本题则是装满有几种方法。

背包容量的问题

因为题意分成两部分，左边部分和右边部分

left - right = target;

left 可以看做是背包的容量

left = sum + right;

(right = sum - left)

so: left = (target + sum)/2

也就是求加法总和

但是：

组合问题

dp[j] 表示：填满j（包括j）这么大容积的包，有dp[j]种方法

填满容量为j - nums[i]的背包，有dp[j - nums[i]]种方法。

那么只要搞到nums[i]的话，凑成dp[j]就有dp[j - nums[i]] 种方法。

例如：dp[j]，j 为5，

• 已经有一个1（nums[i]） 的话，有 dp[4]种方法 凑成 dp[5]。
• 已经有一个2（nums[i]） 的话，有 dp[3]种方法 凑成 dp[5]。
• 已经有一个3（nums[i]） 的话，有 dp[2]中方法 凑成 dp[5]
• 已经有一个4（nums[i]） 的话，有 dp[1]中方法 凑成 dp[5]
• 已经有一个5 （nums[i]）的话，有 dp[0]中方法 凑成 dp[5]

那么凑整dp[5]有多少方法呢，也就是把 所有的 dp[j - nums[i]] 累加起来。

所以求组合类问题的公式，都是类似这种

dp[j] += dp[j - nums[i]]

class Solution {
public:
    int findTargetSumWays(vector<int>& nums, int S) {
        int sum = 0;
        for (int i = 0; i < nums.size(); i++) sum += nums[i];
        if (abs(S) > sum) return 0; // 此时没有方案
        if ((S + sum) % 2 == 1) return 0; // 此时没有方案
        int bagSize = (S + sum) / 2;
        vector<int> dp(bagSize + 1, 0);
        dp[0] = 1;
        for (int i = 0; i < nums.size(); i++) {
            for (int j = bagSize; j >= nums[i]; j--) {
                dp[j] += dp[j - nums[i]];
            }
        }
        return dp[bagSize];
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

474 一和零

本题中strs 数组里的元素就是物品，每个物品都是一个！

而m 和 n相当于是一个背包，两个维度的背包。

**dp[i][j]：最多有i个0和j个1的strs的最大子集的大小为dp[i][j]**。

dp[i][j] 可以由前一个strs里的字符串推导出来，strs里的字符串有zeroNum个0，oneNum个1。

dp[i][j] 就可以是 dp[i - zeroNum][j - oneNum] + 1。

然后我们在遍历的过程中，取dp[i][j]的最大值。

所以递推公式：dp[i][j] = max(dp[i][j], dp[i - zeroNum][j - oneNum] + 1);

此时大家可以回想一下01背包的递推公式：dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);

class Solution {
public:
    int findMaxForm(vector<string>& strs, int m, int n) {
        vector<vector<int>> dp(m + 1, vector<int> (n + 1, 0)); // 默认初始化0
        for (string str : strs) { // 遍历物品
            int oneNum = 0, zeroNum = 0;
            for (char c : str) {
                if (c == '0') zeroNum++;
                else oneNum++;
            }
            for (int i = m; i >= zeroNum; i--) { // 遍历背包容量且从后向前遍历！
                for (int j = n; j >= oneNum; j--) {
                    dp[i][j] = max(dp[i][j], dp[i - zeroNum][j - oneNum] + 1);
                }
            }
        }
        return dp[m][n];
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

class Solution {
public:
    int largestInteger(int num) {
       	string str= to_string(num);
	    string jishu;
	string oushu;
	int j = 0;
	int o = 0; 
//	cout<<str<<endl;
	for(int i = 0; i < str.size(); i++){
		// 分成就 
		if(i%2 == 0){
			jishu[j] = str[i];
			// cout<<jishu[j]<<" ";
			j++;
		}else{
			oushu[o++] = str[i];
		}
	}
	// 对奇数偶数进行排序
	cout<<jishu.size()<<endl;
	sort(jishu.begin(), jishu.end());
	sort(oushu.begin(), oushu.end());
	cout<<jishu.size()<<endl;
	
	// 根据原字符串长度进行遍历 
	string res;
	for(int i = 0; i <str.size(); i++){
		if(i % 2 == 0){
			res[i] = jishu[j--];
		}else{
			res[i] = oushu[o--];
		}
	}
	return atoi(res.c_str()); 
    }
};
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

完全背包理论

定义

有N件物品和一个最多能背重量为W的背包。第i件物品的重量是weight[i]，得到的价值是value[i] 。每件物品都有无限个（也就是可以放入背包多次），求解将哪些物品装入背包里物品价值总和最大。
1

完全背包的dp公式

dp[j] = max(dp[j], dp[j - weight[i] + value[i]]);

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-zAfgYVbI-1651670944360)(https://gitee.com/YDLinGit/blog-img/raw/master/20210729234011.png)]

// 先遍历物品，在遍历背包
void test_CompletePack() {
    vector<int> weight = {1, 3, 4};
    vector<int> value = {15, 20, 30};
    int bagWeight = 4;
    vector<int> dp(bagWeight + 1, 0);
    for(int i = 0; i < weight.size(); i++) { // 遍历物品
        for(int j = weight[i]; j <= bagWeight; j++) { // 遍历背包容量
            dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);
        }
    }
    cout << dp[bagWeight] << endl;
}
int main() {
    test_CompletePack();
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

518. 零钱兑换 II

无线次数— 完全背包问题

但是和纯完全背包问题不同，本题求的是凑的个数

求的是组合数：

5 = 2 + 2 + 1

5 = 2 + 1 + 2

这是一种组合

dp公式：

dp[i] 凑成总金额j的货币组合数为dp[j],考虑coins[i]的组合总和,就是所有的dp[j - coins[i]]（不考虑coins[i]）相加。

dp[i] += dp[i-nums[j]];

如果求组合数就是外层for循环遍历物品，内层for遍历背包。

如果求排列数就是外层for遍历背包，内层for循环遍历物品。

class Solution {
public:
    int change(int amount, vector<int>& coins) {
        vector<int> dp(amount + 1, 0);
        dp[0] = 1;
        for (int i = 0; i < coins.size(); i++) { // 遍历物品
            for (int j = coins[i]; j <= amount; j++) { // 遍历背包
                dp[j] += dp[j - coins[i]];
            }
        }
        return dp[amount];
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13

组合总和IV

377. 组合总和 Ⅳ

难度：中等

给定一个由正整数组成且不存在重复数字的数组，找出和为给定目标正整数的组合的个数。

示例:

nums = [1, 2, 3] target = 4

所有可能的组合为： (1, 1, 1, 1) (1, 1, 2) (1, 2, 1) (1, 3) (2, 1, 1) (2, 2) (3, 1)

请注意，顺序不同的序列被视作不同的组合。

因此输出为 7。

关键点：

1. 多背包问题
2. 遍历顺序

如果求组合数就是外层for循环遍历物品，内层for遍历背包。

如果求排列数就是外层for遍历背包，内层for循环遍历物品。

class Solution {
public:
    int combinationSum4(vector<int>& nums, int target) {
        // 排列问题 重复选取
        // dp[i] += dp[i - nums[j]]
        int n = nums.size();
        vector<int> dp(target+1,0); // target 为背包的大小
        dp[0] = 1;
        // 先遍历背包 在遍历物品
        for(int i = 0; i<=target; ++i){
            for(int j = 0; j < n; ++j){
                // 数组下标注意越界， 累加注意是否整数溢出
                if(i - nums[j] >=0 && dp[i] < INT_MAX - dp[i-nums[j]])
                    dp[i] +=dp[i-nums[j]];
            }
        }
        return dp[target];
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

爬楼梯（进阶版）

原型爬楼梯

70. 爬楼梯

假设你正在爬楼梯。需要 n 阶你才能到达楼顶。

每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？

注意：给定 n 是一个正整数。

示例 1： 输入： 2 输出： 2 解释： 有两种方法可以爬到楼顶。

1. 1 阶 + 1 阶
2. 2 阶

示例 2： 输入： 3 输出： 3 解释： 有三种方法可以爬到楼顶。

1. 1 阶 + 1 阶 + 1 阶
2. 1 阶 + 2 阶
3. 2 阶 + 1 阶

改为：一步一个台阶，两个台阶，三个台阶，…，直到 m个台阶。问有多少种不同的方法可以爬到楼顶呢？

答：其实楼顶就相当于背包的容量n,每一步可以走的台阶数其实就是物品价格m

class Solution {
public:
    int climbStairs(int n) {
        vector<int> dp(n + 1, 0);
        dp[0] = 1;
        for (int i = 1; i <= n; i++) { // 遍历背包
            for (int j = 1; j <= m; j++) { // 遍历物品
                if (i - j >= 0) dp[i] += dp[i - j];
            }
        }
        return dp[n];
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13

而此题只需要将物品m 变为2

零钱兑换

322. 零钱兑换

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

你可以认为每种硬币的数量是无限的。

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

示例 2： 输入：coins = [2], amount = 3 输出：-1

示例 3： 输入：coins = [1], amount = 0 输出：0

示例 4： 输入：coins = [1], amount = 1 输出：1

示例 5： 输入：coins = [1], amount = 2 输出：2

提示：

• 1 <= coins.length <= 12
• 1 <= coins[i] <= 2^31 - 1
• 0 <= amount <= 10^4

与之前的题目：518 零钱兑换（组成目标值硬币的方案数量），本体是求凑成总金额的所需的最少硬币数量

1、确定dp

dp[i] 表示凑足金额为i所需钱币的最少个数为dp[i]

2、确定地推公式

凑足总额为i - coins[j]的最少个数为dp[i - coins[j]]，那么只需要加上一个钱币coins[j]即dp[i - coins[j]] + 1就是dp[i]（考虑coins[j]）

dp[j] = min(dp[j-coins[i]] + 1, dp[i])

3、 初始化

4、 遍历顺序

因为既不算组合也不算排列，因此随便哪种都可以，根据前面写的递推公式的下标，我们采用先遍历背包容量在遍历物品的方式

class Solution {
public:
    int coinChange(vector<int>& coins, int amount) {
        // 因为这道题，如果组合总金额为0则返回0 所以直接将他初始化为INT_MAX 做判断就可以
        vector<int> dp(amount + 1, INT_MAX);
        dp[0] = 0;
        // 遍历背包，遍历物品
        int n = coins.size();
        for(int i = 0; i <=amount; ++i){
            for(int j = 0; j < n; ++j){
                if(i - coins[j] >=0 && dp[i - coins[j]] < INT_MAX){// 注意coins[i - coins[j]] + 1 会报错 = INT_MAX + 1...
                    dp[i] = min(dp[i - coins[j]] + 1, dp[i]);
                }
            }
        }
        // 如果找不到 返回-1
        if(dp[amount] == INT_MAX) return -1;
        return dp[amount];
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

完全平方数

279.完全平方数

给定正整数 n，找到若干个完全平方数（比如 1, 4, 9, 16, …）使得它们的和等于 n。你需要让组成和的完全平方数的个数最少。

给你一个整数 n ，返回和为 n 的完全平方数的 最少数量 。

完全平方数 是一个整数，其值等于另一个整数的平方；换句话说，其值等于一个整数自乘的积。例如，1、4、9 和 16 都是完全平方数，而 3 和 11 不是。

示例 1： 输入：n = 12 输出：3 解释：12 = 4 + 4 + 4

示例 2： 输入：n = 13 输出：2 解释：13 = 4 + 9

提示：

• 1 <= n <= 10^4

题目理解

可能刚看这种题感觉没啥思路，又平方和的，又最小数的。

我来把题目翻译一下：完全平方数就是物品（可以无限件使用），凑个正整数n就是背包，问凑满这个背包最少有多少物品？

1、确定dp[j]

dp[j]：和为j的完全平方数的最少数量为dp[j]

2、递推关系式

dp[j] 可以由dp[j - i * i]推出， dp[j - i * i] + 1 便可以凑成dp[j]。

此时我们要选择最小的dp[j]，所以递推公式：dp[j] = min(dp[j - i * i] + 1, dp[j]);

3、初始化

min -> 初始化为INT_MAX 防止被覆盖

dp[0] = 0;

4、确定遍历顺序

都可以。

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

单词拆分

139 单词拆分

给定一个非空字符串 s 和一个包含非空单词的列表 wordDict，判定 s 是否可以被空格拆分为一个或多个在字典中出现的单词。

说明：

拆分时可以重复使用字典中的单词。

你可以假设字典中没有重复的单词。

示例 1： 输入: s = “leetcode”, wordDict = [“leet”, “code”] 输出: true 解释: 返回 true 因为 “leetcode” 可以被拆分成 “leet code”。

示例 2： 输入: s = “applepenapple”, wordDict = [“apple”, “pen”] 输出: true 解释: 返回 true 因为 “applepenapple” 可以被拆分成 “apple pen apple”。 注意你可以重复使用字典中的单词。

示例 3： 输入: s = “catsandog”, wordDict = [“cats”, “dog”, “sand”, “and”, “cat”] 输出: false

单词就是物品，字符串s就是背包，单词能否组成字符串s，就是问物品能不能把背包装满。

1. 确定dp数组以及下标的含义

dp[i] : 字符串长度为i的话，dp[i]为true，表示可以拆分为一个或多个在字典中出现的单词。

2. 确定递推公式

如果确定dp[j] 是true，且 [j, i] 这个区间的子串出现在字典里，那么dp[i]一定是true。（j < i ）。

所以递推公式是 if([j, i] 个区间的子串出现在字典里 && dp[j]是true) 那么 dp[i] = true。

3. do数组如何初始化

从递归公式中可以看出，dp[i] 的状态依靠 dp[j]是否为true，那么dp[0]就是递归的根基，dp[0]一定要为true，否则递归下去后面都都是false了。

那么dp[0]有没有意义呢？

dp[0]表示如果字符串为空的话，说明出现在字典里。

但题目中说了“给定一个非空字符串 s” 所以测试数据中不会出现i为0的情况，那么dp[0]初始为true完全就是为了推导公式。

下标非0的dp[i]初始化为false，只要没有被覆盖说明都是不可拆分为一个或多个在字典中出现的单词。

4. 确定遍历顺序

题目中说是拆分为一个或多个在字典中出现的单词，所以这是完全背包。

5. 距离推导

   

class Solution {
public:
    bool wordBreak(string s, vector<string>& wordDict) {
        unordered_set<string> wordSet(wordDict.begin(), wordDict.end());
        vector<bool> dp(s.size() + 1, false);
        dp[0] = true;
        for (int i = 1; i <= s.size(); i++) {   // 遍历背包
            for (int j = 0; j < i; j++) {       // 遍历物品
                string word = s.substr(j, i - j); //substr(起始位置，截取的个数)
                if (wordSet.find(word) != wordSet.end() && dp[j]) {
                    dp[i] = true;
                }
            }
        }
        return dp[s.size()];
    }
};	
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

• 时间复杂度：O(n^3)，因为substr返回子串的副本是O(n)的复杂度（这里的n是substring的长度）
• 空间复杂度：O(n)

完全背包问题总结

常见的背包问题

结题步骤

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

背包的递推公式

遍历的方式

01背包问题

完全背包问题：

如果求组合数就是外层for循环遍历物品，内层for遍历背包。

如果求排列数就是外层for遍历背包，内层for循环遍历物品。

他人总结的图片

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-LfpiTA2q-1651670944366)(https://gitee.com/YDLinGit/blog-img/raw/master/%E8%83%8C%E5%8C%85%E9%97%AE%E9%A2%981.jpeg)]

一、打家劫舍

这类题型，主要分为偷与不偷两种情况。

dp[i]: 包括下标i以内的房屋的最多可偷窃的金额

状态转移方程一般为:

dp[i] = max(dp[i-2] + nums[i], dp[i-1])

打家劫舍

198.打家劫舍

你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。

给定一个代表每个房屋存放金额的非负整数数组，计算你 不触动警报装置的情况下 ，一夜之内能够偷窃到的最高金额。

示例 1： 输入：[1,2,3,1] 输出：4 解释：偷窃 1 号房屋 (金额 = 1) ，然后偷窃 3 号房屋 (金额 = 3)。 偷窃到的最高金额 = 1 + 3 = 4 。

示例 2： 输入：[2,7,9,3,1] 输出：12 解释：偷窃 1 号房屋 (金额 = 2), 偷窃 3 号房屋 (金额 = 9)，接着偷窃 5 号房屋 (金额 = 1)。 偷窃到的最高金额 = 2 + 9 + 1 = 12 。

提示：

• 0 <= nums.length <= 100
• 0 <= nums[i] <= 400

1. 确定dp数组以及下标含义

dp[i]：考虑下标i（包括i）以内的房屋，最多可以偷窃的金额为dp[i]。

2. 确定递推公式

决定dp[i]的因素就是第i房间偷还是不偷。

偷第i，要注意隔一个房子，只能考虑i-1

不偷第i，可以考虑i-1的房子

dp[i] = max(dp[i - 2] + nums[i], dp[i - 1]);

3. 初始化

根据含义进行初始化,dp[0] = nums[0],

dp[1] = nums[1];

4. 遍历顺序
5. 距离推导dp数组

class Solution {
public:
    int rob(vector<int>& nums) {
        // 这道题难点在于偷与不偷
        int n = nums.size();
        if(n<=1) return nums[0];
        if(n<=2) return max(nums[0], nums[1]);
        // dp[i] 考虑i以内房间的时候的最大金额
        vector<int> dp(n+1, 0);
        dp[0] = nums[0];
        dp[1] = max(nums[0], nums[1]);
        for(int i = 2; i < n; ++i){
            // 偷 要隔开， 不偷可以考虑i-1的情况
            dp[i] = max(dp[i-2] + nums[i], dp[i-1]);
        }
        return dp[n-1];
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

打家劫舍II

213. 打家劫舍II

你是一个专业的小偷，计划偷窃沿街的房屋，每间房内都藏有一定的现金。这个地方所有的房屋都 围成一圈 ，这意味着第一个房屋和最后一个房屋是紧挨着的。同时，相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警 。

给定一个代表每个房屋存放金额的非负整数数组，计算你 在不触动警报装置的情况下 ，能够偷窃到的最高金额。

示例 1：

输入：nums = [2,3,2] 输出：3 解释：你不能先偷窃 1 号房屋（金额 = 2），然后偷窃 3 号房屋（金额 = 2）, 因为他们是相邻的。

示例 2： 输入：nums = [1,2,3,1] 输出：4 解释：你可以先偷窃 1 号房屋（金额 = 1），然后偷窃 3 号房屋（金额 = 3）。偷窃到的最高金额 = 1 + 3 = 4 。

示例 3： 输入：nums = [0] 输出：0

提示：

• 1 <= nums.length <= 100
• 0 <= nums[i] <= 1000

分析：成环了

则在上一题的基础上分成两种情况。

1. 考虑了首元素，不考虑尾元素
2. 考虑了尾元素，不考虑首元素

class Solution {
public:
    int robRange(vector<int>& nums, int start, int end) {
        int n = end - start + 1;// 注意一下遍历的区间
        if(n<=1) return nums[start];
        if(n<=2) return max(nums[start], nums[start + 1]);
        // dp[i] 考虑i以内房间的时候的最大金额
        vector<int> dp(nums.size(), 0);
        dp[start] = nums[start];
        dp[start+1] = max(nums[start], nums[start+1]);
        // [start+2,end]
        for(int i = start + 2; i < end; ++i){
            // 偷 要隔开， 不偷可以考虑i-1的情况
            dp[i] = max(dp[i-2] + nums[i], dp[i-1]);
        }
        return dp[end-1];// 注意范围的问题
    }

    int rob(vector<int>& nums) {
        int n = nums.size();
        if(n<=1) return nums[0];
        if(n<=2) return max(nums[0], nums[1]);
        int leftRange = robRange(nums, 0, n-1);
        int rightRange = robRange(nums, 1, n);
        return max(leftRange, rightRange);
    }
};
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

打家劫舍 III

337.打家劫舍 III

在上次打劫完一条街道之后和一圈房屋后，小偷又发现了一个新的可行窃的地区。这个地区只有一个入口，我们称之为“根”。 除了“根”之外，每栋房子有且只有一个“父“房子与之相连。一番侦察之后，聪明的小偷意识到“这个地方的所有房屋的排列类似于一棵二叉树”。 如果两个直接相连的房子在同一天晚上被打劫，房屋将自动报警。

计算在不触动警报的情况下，小偷一晚能够盗取的最高金额。

思路：

由于偷与不偷要考虑左右节点

因此只能采取后序遍历

这题其实更像是树上做dp

1. dp数组

dp[i] 下标为0记录不偷该节点所得到的的最大金钱，下标为1记录偷该节点所得到的的最大金钱。

2. 单层遍历的逻辑

• 如果偷当前节点，那么左右孩子就不能偷，val1 = cur->val + left[0] + right[0];
• 如果不偷当前节点，那么左右孩子就可以偷，至于到底偷不偷一定是选一个最大的，所以：val2 = max(left[0], left[1]) + max(right[0], right[1]);

class Solution {
public:
    int rob(TreeNode* root) {
        vector<int> result = robTree(root);
        return max(result[0], result[1]);
    }
    // 长度为2的数组，0：不偷，1：偷
    vector<int> robTree(TreeNode* cur) {
        if (cur == NULL) return vector<int>{0, 0};
        vector<int> left = robTree(cur->left);
        vector<int> right = robTree(cur->right);
        // 偷cur
        int val1 = cur->val + left[0] + right[0];
        // 不偷cur
        int val2 = max(left[0], left[1]) + max(right[0], right[1]);
        return {val2, val1};
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

小结：

dp[i]: 包括下标i以内的房屋的最多可偷窃的金额

状态转移方程一般为:

dp[i] = max(dp[i-2] + nums[i], dp[i-1])

一、股票买卖问题

股票买卖是一个大类

1 买卖股票的最佳时机

121. 买卖股票最佳的时机

给定一个数组 prices ，它的第 i 个元素 prices[i] 表示一支给定股票第 i 天的价格。

你只能选择 某一天 买入这只股票，并选择在 未来的某一个不同的日子 卖出该股票。设计一个算法来计算你所能获取的最大利润。

返回你可以从这笔交易中获取的最大利润。如果你不能获取任何利润，返回 0 。

示例 1：
输入：[7,1,5,3,6,4]
输出：5
解释：在第 2 天（股票价格 = 1）的时候买入，在第 5 天（股票价格 = 6）的时候卖出，最大利润 = 6-1 = 5 。注意利润不能是 7-1 = 6, 因为卖出价格需要大于买入价格；同时，你不能在买入前卖出股票。

示例 2：
输入：prices = [7,6,4,3,1]
输出：0
解释：在这种情况下, 没有交易完成, 所以最大利润为 0。

1、确定dp数组

dp[i][0] 表示第i天持有的股票所得最多现金

dp[i][1] 表示第i天不持有股票的所得最多现金

2、递推公式

dp[i][0] 第i天持有股票

• 第i-1天就持有股票，那么就保持现状，所得现金就是昨天持有股票的所得现金 即：dp[i - 1][0]
• 第i天买入股票，所得现金就是买入今天的股票后所得现金即：-prices[i]

既dp[i][0] = max(dp[i-1][0], -prices[i]);

dp[i][1] 第i天不持有股票

• 第i-1天就不持有股票，那么就保持现状，所得现金就是昨天不持有股票的所得现金 即：dp[i - 1][1]
• 第i天卖出股票，所得现金就是按照今天股票佳价格卖出后所得现金即：prices[i] + dp[i - 1][0]

dp[i][1] = max(dp[i-1][1], dp[i][0] + prices[i]);

3. dp数组初始化

根据dp定义进行初始化：

• 第0天dp[0][0] -= prices[0]
• 第0天dp[0][1] = 0;

4. 遍历顺序

dp[i]由dp[i-1]而来，所以由前向后遍历

5. 距离推导dp数组

以示例1，输入7,1,5,3,6,4]为例，dp数组状态如下：

2 买卖股票的最佳时机II

122.买卖股票的最佳时机II

给定一个数组，它的第 i 个元素是一支给定股票第 i 天的价格。

设计一个算法来计算你所能获取的最大利润。你可以尽可能地完成更多的交易（多次买卖一支股票）。

注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。

示例 1:
输入: [7,1,5,3,6,4]
输出: 7
解释: 在第 2 天（股票价格 = 1）的时候买入，在第 3 天（股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5-1 = 4。随后，在第 4 天（股票价格 = 3）的时候买入，在第 5 天（股票价格 = 6）的时候卖出, 这笔交易所能获得利润 = 6-3 = 3 。

示例 2:
输入: [1,2,3,4,5]
输出: 4
解释: 在第 1 天（股票价格 = 1）的时候买入，在第 5 天 （股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5-1 = 4 。注意你不能在第 1 天和第 2 天接连购买股票，之后再将它们卖出。因为这样属于同时参与了多笔交易，你必须在再次购买前出售掉之前的股票。

示例 3:
输入: [7,6,4,3,1]
输出: 0
解释: 在这种情况下, 没有交易完成, 所以最大利润为 0。

提示：

• 1 <= prices.length <= 3 * 10 ^ 4
• 0 <= prices[i] <= 10 ^ 4

与上一题最大的区别就是可以买入多次，要统计利润总和

就是当天持有股票的价值：

dp[i][0] =max(dp[i - 1][0], dp[i - 1][1] - prices[i]);

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

3 买卖股票的最佳时机III

123.买卖股票的最佳时机III

给定一个数组，它的第 i 个元素是一支给定的股票在第 i 天的价格。

设计一个算法来计算你所能获取的最大利润。你最多可以完成 两笔 交易。

注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。

示例 1: 输入：prices = [3,3,5,0,0,3,1,4] 输出：6 解释：在第 4 天（股票价格 = 0）的时候买入，在第 6 天（股票价格 = 3）的时候卖出，这笔交易所能获得利润 = 3-0 = 3 。随后，在第 7 天（股票价格 = 1）的时候买入，在第 8 天 （股票价格 = 4）的时候卖出，这笔交易所能获得利润 = 4-1 = 3。

示例 2： 输入：prices = [1,2,3,4,5] 输出：4 解释：在第 1 天（股票价格 = 1）的时候买入，在第 5 天 （股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5-1 = 4。注意你不能在第 1 天和第 2 天接连购买股票，之后再将它们卖出。因为这样属于同时参与了多笔交易，你必须在再次购买前出售掉之前的股票。

示例 3： 输入：prices = [7,6,4,3,1] 输出：0 解释：在这个情况下, 没有交易完成, 所以最大利润为0。

示例 4： 输入：prices = [1] 输出：0

提示：

• 1 <= prices.length <= 10^5
• 0 <= prices[i] <= 10^5

与之前不同的是，关键在于至多买卖两次，就是可以买卖一次，可以买卖两次，也可以不买卖

1. 确定dp数组以及下标的含义

一天一共就有五个状态，

1. 没有操作
2. 第一次买入
3. 第一次卖出
4. 第二次买入
5. 第二次卖出

dp[i][j]中 i表示第i天，j为 [0 - 4] 五个状态，dp[i][j]表示第i天状态j所剩最大现金。

2. 确定dp公式

dp[i][1]，表示的是第i天，买入股票的状态，并不是说一定要第i天买入股票，这是很多同学容易陷入的误区。

dp[i][1]

• 操作一：第i天买入股票了，那么dp[i][1] = dp[i-1][0] - prices[i]
• 操作二：第i天没有操作，而是沿用前一天买入的状态，即：dp[i][1] = dp[i - 1][1]

dp[i][1] = max(dp[i-1][0] - price[i], dp[i-1][1]);

同理dp[i][2]也有两个操作：

• 操作一：第i天卖出股票了，那么dp[i][2] = dp[i - 1][1] + prices[i]
• 操作二：第i天没有操作，沿用前一天卖出股票的状态，即：dp[i][2] = dp[i - 1][2]

dp[i][2] = max(dp[i-1][1] + pruce[i], dp[i-1][2])

同理：

dp[i][3] = max(dp[i - 1][3], dp[i - 1][2] - prices[i]);

dp[i][4] = max(dp[i - 1][4], dp[i - 1][3] + prices[i]);

3. dp初始化

第0天没有操作，这个最容易想到，就是0，即：dp[0][0] = 0;

第0天做第一次买入的操作，dp[0][1] = -prices[0];

第0天做第一次卖出的操作 dp[0][2] = 0

第0天做第二次买入的操作 dp[0][3] = -prices[0]

第0天做第二次卖出的操作 dp[0][4] = 0

4. 遍历顺序

5. 举例推导dp数组

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-xAxidww6-1651670944375)(https://gitee.com/YDLinGit/blog-img/raw/master/20201228181724295.png)]

红色框为最后两次卖出的状态。最大的时候一定是卖出的状态，而两次卖出的状态现金最大一定是最后一次卖出。

最终最大利润是dp[4][4]

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int n = prices.size();
        vector<vector<int>> dp(n, vector<int>(5,0));
        //dp[i][j]表示第i天下第j状态的最大利润
        // i = 1 第一次买入;i = 2 第一次卖出;i = 3 第二次买入; i= 4 第二次卖出
        dp[0][0] = 0;
        dp[0][1] = -prices[0];
        dp[0][2] = 0;
        dp[0][3] = -prices[0];
        dp[0][4] = 0;
        for(int i = 1; i<n; ++i){
            dp[i][1] = max(dp[i-1][1], dp[i-1][0] - prices[i]);
            dp[i][2] = max(dp[i-1][2], dp[i-1][1] + prices[i]);
            dp[i][3] = max(dp[i-1][3], dp[i-1][2] - prices[i]);
            dp[i][4] = max(dp[i-1][4], dp[i-1][3] + prices[i]);
        }
        return dp[n-1][4];
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

4 买卖股票的最佳时机IV

188.买卖股票的最佳时机IV

与前面一题最大的区别就是变成了k次。

1. dp初始化

j的状态表示为：

• 0 表示不操作
• 1 第一次买入
• 2 第一次卖出
• 3 第二次买入
• 4 第二次卖出
• …

除了0以外，偶数就是卖出，奇数就是买入。

要求是至多有K笔交易，那么j的范围就定义为 2 * k + 1 就可以了。

2. 递推公式

与之前一样，但是通过1的规律，我们可以类比得出如下的状态转移

for (int j = 0; j < 2 * k - 1; j += 2) {
    dp[i][j + 1] = max(dp[i - 1][j + 1], dp[i - 1][j] - prices[i]);
    dp[i][j + 2] = max(dp[i - 1][j + 2], dp[i - 1][j + 1] + prices[i]);
}
1
2
3
4

3. 初始化状态

可以推出dp[0][j]当j为奇数的时候都初始化为 -prices[0]

for (int j = 1; j < 2 * k; j += 2) {
    dp[0][j] = -prices[0];
}
1
2
3

4. 确定遍历顺序

5. 距离推导dp数组

class Solution {
public:
    int maxProfit(int k, vector<int>& prices) {

        if (prices.size() == 0) return 0;
        vector<vector<int>> dp(prices.size(), vector<int>(2 * k + 1, 0));
        for (int j = 1; j < 2 * k; j += 2) {
            dp[0][j] = -prices[0];
        }
        for (int i = 1;i < prices.size(); i++) {
            for (int j = 0; j < 2 * k - 1; j += 2) {
                dp[i][j + 1] = max(dp[i - 1][j + 1], dp[i - 1][j] - prices[i]);
                dp[i][j + 2] = max(dp[i - 1][j + 2], dp[i - 1][j + 1] + prices[i]);
            }
        }
        return dp[prices.size() - 1][2 * k];
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

5 最佳买卖股票时机含冷冻期

309.最佳买卖股票时机含冷冻期

给定一个整数数组，其中第 i 个元素代表了第 i 天的股票价格 。

设计一个算法计算出最大利润。在满足以下约束条件下，你可以尽可能地完成更多的交易（多次买卖一支股票）:

• 你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。
• 卖出股票后，你无法在第二天买入股票 (即冷冻期为 1 天)。

示例: 输入: [1,2,3,0,2] 输出: 3 解释: 对应的交易状态为: [买入, 卖出, 冷冻期, 买入, 卖出]

在总利润和的基础上加了一个冷冻期，状态变了

1. 确定dp数组及下标含义

• 状态一：买入股票状态（今天买入股票，或者是之前就买入了股票然后没有操作）
• 卖出股票状态，这里就有两种卖出股票状态
  • 状态二：两天前就卖出了股票，度过了冷冻期，一直没操作，今天保持卖出股票状态
  • 状态三：今天卖出了股票
• 状态四：今天为冷冻期状态，但冷冻期状态不可持续，只有一天！

注意这里的每一个状态，例如状态一，是买入股票状态并不是说今天已经就买入股票，而是说保存买入股票的状态即：可能是前几天买入的，之后一直没操作，所以保持买入股票的状态。

2. 确定递推公式

(1)达到买入股票(状态1)，既dp[i][0]，有两个具体操作：

• 操作一：前一天就是持有股票状态（状态一），dp[i][0] = dp[i - 1][0]
• 操作二：今天买入了，有两种情况
  • 前一天是冷冻期（状态四），dp[i - 1][3] - prices[i]
  • 前一天是保持卖出股票状态（状态二），dp[i - 1][1] - prices[i]

所以操作二取最大值，即：max(dp[i - 1][3], dp[i - 1][1]) - prices[i]

那么dp[i][0] = max(dp[i - 1][0], max(dp[i - 1][3], dp[i - 1][1]) - prices[i]);

(2) 达到保持卖出股票状态（状态二）即：dp[i][1]，有两个具体操作：

• 操作一：前一天就是状态二
• 操作二：前一天是冷冻期（状态四）

dp[i][1] = max(dp[i - 1][1], dp[i - 1][3]);

(3) 达到今天就卖出股票状态（状态三），即：dp[i][2] ，只有一个操作：

• 操作一：昨天一定是买入股票状态（状态一），今天卖出

即：dp[i][2] = dp[i - 1][0] + prices[i];

(4) 达到冷冻期状态（状态四），即：dp[i][3]，只有一个操作：

• 操作一：昨天卖出了股票（状态三）

dp[i][3] = dp[i - 1][2];

综上分析，递推代码如下：

dp[i][0] = max(dp[i - 1][0], max(dp[i - 1][3], dp[i - 1][1]) - prices[i]);
dp[i][1] = max(dp[i - 1][1], dp[i - 1][3]);
dp[i][2] = dp[i - 1][0] + prices[i];
dp[i][3] = dp[i - 1][2];
1
2
3
4

3. 如何初始化

如果是持有股票状态（状态一）那么：dp[0][0] = -prices[0]，买入股票所剩现金为负数。

保持卖出股票状态（状态二），第0天没有卖出dp[0][1]初始化为0就行，

今天卖出了股票（状态三），同样dp[0][2]初始化为0，因为最少收益就是0，绝不会是负数。

同理dp[0][3]也初始为0。

4. 确定遍历顺序
5. 距离推导dp数组

最后结果是取 状态二，状态三，和状态四的最大值，不少同学会把状态四忘了，状态四是冷冻期，最后一天如果是冷冻期也可能是最大值。

• 时间复杂度：$O(n)$
• 空间复杂度：$O(n)$

6 买卖股票的最佳时机含手续费

714.买卖股票的最佳时机含手续费

与122不同的是，要算手续费,买是不需要算手续费的

dp方程

第i天持有股票即dp[i][0]

dp[i][0] = max(dp[i - 1][0], dp[i - 1][1] - prices[i]);

第i天不持有股票即dp[i][1]的情况

dp[i][1] = max(dp[i - 1][1], dp[i - 1][0] + prices[i] - fee)

• 第i-1天就不持有股票，那么就保持现状，所得现金就是昨天不持有股票的所得现金 即：dp[i - 1][1]
• 第i天卖出股票，所得现金就是按照今天股票价格卖出后所得现金，注意这里需要有手续费了即：dp[i - 1][0] + prices[i] - fee

class Solution {
public:
    int maxProfit(vector<int>& prices, int fee) {
        // 其实含手续费就是在卖出的时候不一样
        int n = prices.size();
        if(n <=1) return 0;
        vector<vector<int>> dp(n, vector<int>(2,0));
        dp[0][0] = -prices[0];
        dp[0][1] = 0;
        for(int i = 1; i < n; ++i){
            dp[i][0] = max(dp[i - 1][0], dp[i - 1][1] - prices[i]);
            dp[i][1] = max(dp[i - 1][1], dp[i - 1][0] + prices[i] - fee);
        }
        return dp[n-1][1];
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

二、股票问题总结

一、子字符串问题

1 最长递增子序列

300.最长递增子序列

力扣题目链接(opens new window)

给你一个整数数组 nums ，找到其中最长严格递增子序列的长度。

子序列是由数组派生而来的序列，删除（或不删除）数组中的元素而不改变其余元素的顺序。例如，[3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的子序列。

示例 1： 输入：nums = [10,9,2,5,3,7,101,18] 输出：4 解释：最长递增子序列是 [2,3,7,101]，因此长度为 4 。

示例 2： 输入：nums = [0,1,0,3,2,3] 输出：4

示例 3： 输入：nums = [7,7,7,7,7,7,7] 输出：1

提示：

• 1 <= nums.length <= 2500
• -10^4 <= nums[i] <= 104

1. dp数组的定义

dp[i]表示i之前包括i的以nums[i]结尾最长上升子序列的长度

2. 状态转移方程

位置i的最长升序子序列等于j从0到i-1各个位置的最长升序子序列 + 1 的最大值。

if (nums[i] > nums[j]) dp[i] = max(dp[i], dp[j] + 1);
1

3. 初始化
4. 遍历顺序
5. 距离说明

class Solution {
public:
    int lengthOfLIS(vector<int>& nums) {
        if (nums.size() <= 1) return nums.size();
        vector<int> dp(nums.size(), 1);
        int result = 0;
        for (int i = 1; i < nums.size(); i++) {
            for (int j = 0; j < i; j++) {
                if (nums[i] > nums[j]) dp[i] = max(dp[i], dp[j] + 1);
            }
            if (dp[i] > result) result = dp[i]; // 取长的子序列
        }
        return result;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

2 最长连续递增序列

674. 最长连续递增序列

给定一个未经排序的整数数组，找到最长且 连续递增的子序列，并返回该序列的长度。

连续递增的子序列 可以由两个下标 l 和 r（l < r）确定，如果对于每个 l <= i < r，都有 nums[i] < nums[i + 1] ，那么子序列 [nums[l], nums[l + 1], …, nums[r - 1], nums[r]] 就是连续递增子序列。

示例 1： 输入：nums = [1,3,5,4,7] 输出：3 解释：最长连续递增序列是 [1,3,5], 长度为3。 尽管 [1,3,5,7] 也是升序的子序列, 但它不是连续的，因为 5 和 7 在原数组里被 4 隔开。

示例 2： 输入：nums = [2,2,2,2,2] 输出：1 解释：最长连续递增序列是 [2], 长度为1。

提示：

• 0 <= nums.length <= 10^4
• -10^9 <= nums[i] <= 10^9

与上一题最大的区别就是连续二字

1. 确定dp数组（dp table）以及下标的含义

dp[i]：以下标i为结尾的数组的连续递增的子序列长度为dp[i]。

2. 确定递推公式

如果 nums[i + 1] > nums[i]，那么以 i+1 为结尾的数组的连续递增的子序列长度 一定等于 以i为结尾的数组的连续递增的子序列长度 + 1 。

for (int i = 0; i < nums.size() - 1; i++) {
    if (nums[i + 1] > nums[i]) { // 连续记录
        dp[i + 1] = dp[i] + 1; // 递推公式
    }
}
1
2
3
4
5

3. 初始化
4. 遍历舒徐
5. 举例分析

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

3 最长重复子数组

718. 最长重复子数组

给两个整数数组 A 和 B ，返回两个数组中公共的、长度最长的子数组的长度。

示例：

输入： A: [1,2,3,2,1] B: [3,2,1,4,7] 输出：3 解释： 长度最长的公共子数组是 [3, 2, 1] 。

提示：

• 1 <= len(A), len(B) <= 1000
• 0 <= A[i], B[i] < 100

这道题基本上就是上课讲动态规划的经典例题了。

1. 确定dp

以下标i - 1为结尾的A，和以下标j - 1为结尾的B，最长重复子数组长度为dp[i][j]。

2. 确定递推公式

dp[i][j] = dp[i - 1][j - 1] + 1;

for (int i = 1; i <= A.size(); i++) {
    for (int j = 1; j <= B.size(); j++) {
        if (A[i - 1] == B[j - 1]) {
            dp[i][j] = dp[i - 1][j - 1] + 1;
        }
        if (dp[i][j] > result) result = dp[i][j];
    }
}
1
2
3
4
5
6
7
8

3. dp数组如何初始化

dp[1][1] = dp[0][0] + 1，只有dp[0][0]初始为0

4. 遍历顺序
5. 举例推导

class Solution {
public:
    int findLength(vector<int>& A, vector<int>& B) {
        vector<vector<int>> dp (A.size() + 1, vector<int>(B.size() + 1, 0));
        int result = 0;
        for (int i = 1; i <= A.size(); i++) {
            for (int j = 1; j <= B.size(); j++) {
                if (A[i - 1] == B[j - 1]) {
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                }
                if (dp[i][j] > result) result = dp[i][j];
            }
        }
        return result;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

滚动数组

我们可以看出dp[i][j]都是由dp[i - 1][j - 1]推出。那么压缩为一维数组，也就是dp[j]都是由dp[j - 1]推出。

也就是相当于可以把上一层dp[i - 1][j]拷贝到下一层dp[i][j]来继续用。

此时遍历B数组的时候，就要从后向前遍历，这样避免重复覆盖。

class Solution {
public:
    int findLength(vector<int>& A, vector<int>& B) {
        vector<int> dp(vector<int>(B.size() + 1, 0));
        int result = 0;
        for (int i = 1; i <= A.size(); i++) {
            for (int j = B.size(); j > 0; j--) {
                if (A[i - 1] == B[j - 1]) {
                    dp[j] = dp[j - 1] + 1;
                } else dp[j] = 0; // 注意这里不相等的时候要有赋0的操作
                if (dp[j] > result) result = dp[j];
            }
        }
        return result;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

• 时间复杂度：$O(n\times m)$，n 为A长度，m为B长度
• 空间复杂度：$O(m)$

4 最长公共子序列

1143.最长公共子序列

给定两个字符串 text1 和 text2，返回这两个字符串的最长公共子序列的长度。

一个字符串的 子序列 是指这样一个新的字符串：它是由原字符串在不改变字符的相对顺序的情况下删除某些字符（也可以不删除任何字符）后组成的新字符串。

例如，“ace” 是 “abcde” 的子序列，但 “aec” 不是 “abcde” 的子序列。两个字符串的「公共子序列」是这两个字符串所共同拥有的子序列。

若这两个字符串没有公共子序列，则返回 0。

示例 1:

输入：text1 = “abcde”, text2 = “ace”
输出：3
解释：最长公共子序列是 “ace”，它的长度为 3。

示例 2:
输入：text1 = “abc”, text2 = “abc”
输出：3
解释：最长公共子序列是 “abc”，它的长度为 3。

示例 3:
输入：text1 = “abc”, text2 = “def”
输出：0
解释：两个字符串没有公共子序列，返回 0。

提示:

• 1 <= text1.length <= 1000
• 1 <= text2.length <= 1000 输入的字符串只含有小写英文字符。

举个栗子分析就能发现dp状态转移方程

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

5 不相交的线

1035.不相交的线

我们在两条独立的水平线上按给定的顺序写下 A 和 B 中的整数。

现在，我们可以绘制一些连接两个数字 A[i] 和 B[j] 的直线，只要 A[i] == B[j]，且我们绘制的直线不与任何其他连线（非水平线）相交。

以这种方法绘制线条，并返回我们可以绘制的最大连线数。

输入：nums1 = [1,4,2], nums2 = [1,2,4]
输出：2
解释：可以画出两条不交叉的线，如上图所示。
但无法画出第三条不相交的直线，因为从 nums1[1]=4 到 nums2[2]=4 的直线将与从 nums1[2]=2 到 nums2[1]=2 的直线相交。

这道题 有两个关键的地方

不能改变顺序

不可相交

class Solution {
public:
    int maxUncrossedLines(vector<int>& nums1, vector<int>& nums2) {
        // 这道题其实就是最长公共子序列的变形
        //dp[i][j] 表示以i-1为结尾的nums1与j-1为结尾的nums2的最长公共字符串
        int n = nums1.size();
        int m = nums2.size();
        if(n==0 || m == 0) return 0;
        vector<vector<int>> dp(n+1, vector<int>(m+1,0));
        int res = 0;
        for(int i = 1; i <= n; ++i){
            for(int j = 1; j<=m; ++j){
                if(nums1[i-1] == nums2[j-1]){
                    dp[i][j] = dp[i-1][j-1] + 1;
                }else{
                    dp[i][j] = max(dp[i-1][j], dp[i][j-1]);
                }
                res = max(dp[i][j], res);
            }
        }
        return res;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

6 最大子数组和

53. 最大子数组和

关键点在于定义dp

dp[i] 表示加入nums[i]后连续数组的最大和

            dp[i] = max(dp[i-1] + nums[i], nums[i]);
            maxSum = max(dp[i],maxSum);
1
2

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        // 动态规划
        int maxSum = INT_MIN;
        int n = nums.size();
        vector<int>dp(n);
        dp[0] = nums[0];
        maxSum = nums[0];      
        for(int i  = 1; i < nums.size(); i++){
            dp[i] = max(dp[i-1] + nums[i], nums[i]);
            maxSum = max(dp[i],maxSum);
        }
        return maxSum;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

7 判断子序列

392. 判断子序列

class Solution {
public:
    bool isSubsequence(string s, string t) {
        int n = s.size();
        int m = t.size();
        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(s[i-1] == t[j-1]){
                    // 相等的长度+1
                    // dp[i-1][j-1]
                    dp[i][j] = dp[i-1][j-1] + 1;
                }else{
                    // 如果不相等,需要删除
                    // 则看的是s[i-1]与t[j-2]的结果
                    // dp[j-1]
                    dp[i][j] = dp[i][j-1];
                }
            }
        }
        if(dp[n][m] == n) return true;
        else return false;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

8 编辑距离

72. 编辑距离

class Solution {
public:
    int minDistance(string word1, string word2) {
        // 动态规划
        // dp[i][j]表示i-1为结尾的word1字符串与j-1结尾的字符串的最小编辑距离
        int n = word1.size();
        int m = word2.size();
        vector<vector<int>> dp(n+1,vector<int>(m+1,0));
        // 初始化
        // dp[i][0]相当于i结尾的字符串与空字符串的编辑距离
        for(int i = 0; i <=n; ++i) dp[i][0] = i;
        for(int j = 0; j <=m; ++j) dp[0][j] = j;
        for(int i = 1; i <= n; ++i){
            for(int j = 1; j <= m; ++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], dp[i-1][j], dp[i-1][j-1]}) + 1;
                }
            }
        }
        return dp[n][m];
    }
};
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

9 两个字符串的删除操作

583. 两个字符串的删除操作

class Solution {
public:
    int minDistance(string word1, string word2) {
        // dp[i][j] 以i-1的word1字符串与以j-1的word2字符串的相同的最小步数
        int n = word1.size();
        int m = word2.size();
        vector<vector<int>> dp(n+1, vector<int>(m+1));
        // 初始化
        for(int i = 0; i <= n; ++i) dp[i][0] = i;
        for(int j = 1; j<= m; ++j) dp[0][j] = j;
        // 分为相等和不相等两大类
        for(int i = 1; i<=n; ++i){
            for(int j = 1; j<=m; ++j){
                if(word1[i-1] == word2[j-1]){
                    dp[i][j] = dp[i-1][j-1];
                }else{
                    // 有三种情况
                    // word1 删除一个，word2删除一个  word1,word2删除
                    dp[i][j] = min({dp[i-1][j] + 1, dp[i][j-1] + 1, dp[i-1][j-1] + 2});
                }
            }
        }
        return dp[n][m];
    }
};
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

10 编辑距离问题小结：

判断子序列

动态规划：392.判断子序列 (opens new window)给定字符串 s 和 t ，判断 s 是否为 t 的子序列。

dp[i][j]表示以下标i-1为结尾的字符串s，和以下标j-1为结尾的字符串t，相同子序列的长度为dp[i][j]。

这道题目 其实是可以用双指针或者贪心的的，但是我在开篇的时候就说了这是编辑距离的入门题目，因为从题意中我们也可以发现，只需要计算删除的情况，不用考虑增加和替换的情况。

• if (s[i - 1] == t[j - 1])
  • t中找到了一个字符在s中也出现了
• if (s[i - 1] != t[j - 1])
  • 相当于t要删除元素，继续匹配

状态转移方程：

if (s[i - 1] == t[j - 1]) dp[i][j] = dp[i - 1][j - 1] + 1;
else dp[i][j] = dp[i][j - 1];
1
2

不同的子序列

动态规划：115.不同的子序列 (opens new window)给定一个字符串 s 和一个字符串 t ，计算在 s 的子序列中 t 出现的个数。

本题虽然也只有删除操作，不用考虑替换增加之类的，但相对于动态规划：392.判断子序列 (opens new window)就有难度了，这道题目双指针法可就做不了。

1. 当s[i - 1] 与 t[j - 1]相等时，dp[i][j]可以有两部分组成。

• 一部分是用s[i - 1]来匹配，那么个数为dp[i - 1][j - 1]。
• 一部分是不用s[i - 1]来匹配，个数为dp[i - 1][j]。

这里可能有同学不明白了，为什么还要考虑 不用s[i - 1]来匹配，都相同了指定要匹配啊。

例如： s：bagg 和 t：bag ，s[3] 和 t[2]是相同的，但是字符串s也可以不用s[3]来匹配，即用s[0]s[1]s[2]组成的bag。

当然也可以用s[3]来匹配，即：s[0]s[1]s[3]组成的bag。

所以当s[i - 1] 与 t[j - 1]相等时，dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j];

2. 当s[i - 1] 与 t[j - 1]不相等时，dp[i][j]只有一部分组成，不用s[i - 1]来匹配，即：dp[i - 1][j]

所以递推公式为：dp[i][j] = dp[i - 1][j];

状态转移方程：

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

两个字符串的删除操作

动态规划：583.两个字符串的删除操作 (opens new window)给定两个单词 word1 和 word2，找到使得 word1 和 word2 相同所需的最小步数，每步可以删除任意一个字符串中的一个字符。

1. 当word1[i - 1] 与 word2[j - 1]相同的时候
2. 当word1[i - 1] 与 word2[j - 1]不相同的时候

当word1[i - 1] 与 word2[j - 1]相同的时候，dp[i][j] = dp[i - 1][j - 1];

当word1[i - 1] 与 word2[j - 1]不相同的时候，有三种情况：

情况一：删word1[i - 1]，最少操作次数为dp[i - 1][j] + 1

情况二：删word2[j - 1]，最少操作次数为dp[i][j - 1] + 1

情况三：同时删word1[i - 1]和word2[j - 1]，操作的最少次数为dp[i - 1][j - 1] + 2

那最后当然是取最小值，所以当word1[i - 1] 与 word2[j - 1]不相同的时候，递推公式：dp[i][j] = min({dp[i - 1][j - 1] + 2, dp[i - 1][j] + 1, dp[i][j - 1] + 1});

状态转移方程：

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] + 2, dp[i - 1][j] + 1, dp[i][j - 1] + 1});
}
1
2
3
4
5

编辑距离

动态规划：72.编辑距离 (opens new window)给你两个单词 word1 和 word2，请你计算出将 word1 转换成 word2 所使用的最少操作数 。

编辑距离终于来了，有了前面三道题目的铺垫，应该有思路了，本题是两个字符串可以增删改，比 动态规划：判断子序列 (opens new window)，动态规划：不同的子序列 (opens new window)，动态规划：两个字符串的删除操作 (opens new window)都要复杂的多。

在确定递推公式的时候，首先要考虑清楚编辑的几种操作，整理如下：

• if (word1[i - 1] == word2[j - 1])
  • 不操作
• if (word1[i - 1] != word2[j - 1])
  • 增
  • 删
  • 换

也就是如上四种情况。

if (word1[i - 1] == word2[j - 1]) 那么说明不用任何编辑，dp[i][j] 就应该是 dp[i - 1][j - 1]，即dp[i][j] = dp[i - 1][j - 1];

此时可能有同学有点不明白，为啥要即dp[i][j] = dp[i - 1][j - 1]呢？

那么就在回顾上面讲过的dp[i][j]的定义，word1[i - 1] 与 word2[j - 1]相等了，那么就不用编辑了，以下标i-2为结尾的字符串word1和以下标j-2为结尾的字符串word2的最近编辑距离dp[i - 1][j - 1] 就是 dp[i][j]了。

在下面的讲解中，如果哪里看不懂，就回想一下dp[i][j]的定义，就明白了。

在整个动规的过程中，最为关键就是正确理解dp[i][j]的定义！

if (word1[i - 1] != word2[j - 1])，此时就需要编辑了，如何编辑呢？

1. 操作一：word1增加一个元素，使其word1[i - 1]与word2[j - 1]相同，那么就是以下标i-2为结尾的word1 与 i-1为结尾的word2的最近编辑距离 加上一个增加元素的操作。

即 dp[i][j] = dp[i - 1][j] + 1;

2. 操作二：word2添加一个元素，使其word1[i - 1]与word2[j - 1]相同，那么就是以下标i-1为结尾的word1 与 j-2为结尾的word2的最近编辑距离 加上一个增加元素的操作。

即 dp[i][j] = dp[i][j - 1] + 1;

这里有同学发现了，怎么都是添加元素，删除元素去哪了。

word2添加一个元素，相当于word1删除一个元素，例如 word1 = “ad” ，word2 = “a”，word2添加一个元素d，也就是相当于word1删除一个元素d，操作数是一样！

3. 操作三：替换元素，word1替换word1[i - 1]，使其与word2[j - 1]相同，此时不用增加元素，那么以下标i-2为结尾的word1 与 j-2为结尾的word2的最近编辑距离 加上一个替换元素的操作。

即 dp[i][j] = dp[i - 1][j - 1] + 1;

综上，当 if (word1[i - 1] != word2[j - 1]) 时取最小的，即：dp[i][j] = min({dp[i - 1][j - 1], dp[i - 1][j], dp[i][j - 1]}) + 1;

递归公式代码如下：

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], dp[i - 1][j], dp[i][j - 1]}) + 1;
}
1
2
3
4
5
6

11 回文子串

647. 回文子串

给定一个字符串，你的任务是计算这个字符串中有多少个回文子串。

具有不同开始位置或结束位置的子串，即使是由相同的字符组成，也会被视作不同的子串。

示例 1：

输入：“abc” 输出：3 解释：三个回文子串: “a”, “b”, “c”

示例 2：

输入：“aaa” 输出：6 解释：6个回文子串: “a”, “a”, “a”, “aa”, “aa”, “aaa”

提示：

输入的字符串长度不会超过 1000

1. 确定dp数组

布尔类型的dp[i][j]：表示区间范围[i,j] （注意是左闭右闭）的子串是否是回文子串，如果是dp[i][j]为true，否则为false。

2. 确定地推公式

在确定地推公式时，就要分析如下几种情况。

1. 当s[i]与s[j]不相等，那没啥好说的了，dp[i][j]一定是false。
2. 当s[i]与s[j]相等时，这就复杂一些了，有如下三种情况

• 情况一：下标i 与 j相同，同一个字符例如a，当然是回文子串
• 情况二：下标i 与 j相差为1，例如aa，也是回文子串
• 情况三：下标：i 与 j相差大于1的时候，例如cabac
  • 此时s[i]与s[j]已经相同了，我们看i到j区间是不是回文子串就看aba是不是回文就可以了，那么aba的区间就是 i+1 与 j-1区间
  • 这个区间是不是回文就看dp[i + 1][j - 1]是否为true。

if (s[i] == s[j]) {
    if (j - i <= 1) { // 情况一 和 情况二
        result++;
        dp[i][j] = true;
    } else if (dp[i + 1][j - 1]) { // 情况三
        result++;
        dp[i][j] = true;
    }
}
1
2
3
4
5
6
7
8
9

3. 数组初始化

初始化的时候全部为false

4. 遍历顺序

从递推方程可以看出，由于dp[i+1][j-1]在dp[i][j]下方，未初始化就使用了

因此需要从下到上从左到右遍历

5. 举例推导

输入：“aaa”

图中有6个true，所以就是有6个回文子串。

注意因为dp[i][j]的定义，所以j一定是大于等于i的，那么在填充dp[i][j]的时候一定是只填充右上半部分。

class Solution {
public:
    int countSubstrings(string s) {
        vector<vector<bool>> dp(s.size(), vector<bool>(s.size(), false));
        int result = 0;
        for (int i = s.size() - 1; i >= 0; i--) {  // 注意遍历顺序
            for (int j = i; j < s.size(); j++) {
                if (s[i] == s[j]) {
                    if (j - i <= 1) { // 情况一 和 情况二
                        result++;
                        dp[i][j] = true;
                    } else if (dp[i + 1][j - 1]) { // 情况三
                        result++;
                        dp[i][j] = true;
                    }
                }
            }
        }
        return result;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

12 最长回文子串

给你一个字符串 s，找到 s 中最长的回文子串。

5. 最长回文子串

示例 1：

输入：s = “babad”
输出：“bab”
解释：“aba” 同样是符合题意的答案。
示例 2：

输入：s = “cbbd”
输出：“bb”

最大的区别在于：

这里只需要统计最长的回文串，而不是统计回文串

所以只需修改的：

添加最大的连续长度的判断

                if(dp[i][j] && j - i + 1 >= maxLen){
                        maxLen = j - i + 1;
                        start = i;
                        end = j;
                }
1
2
3
4
5

class Solution {
public:
    string longestPalindrome(string s) {
        vector<vector<bool>> dp(s.size(), vector<bool>(s.size(), false));
        if(s.size() <= 1 ) return s;
        int result = 0;
        int maxLen = 0;
        int start = 0;
        int end = 0;
        for (int i = s.size() - 1; i >= 0; i--) {  // 注意遍历顺序
            for (int j = i; j < s.size(); j++) {
                if (s[i] == s[j]) {
                    if (j - i <= 1) { // 情况一 和 情况二
                        dp[i][j] = true;
                    } else if (dp[i + 1][j - 1]) { // 情况三
                        result++;
                        dp[i][j] = true;
                    }
                }
                if(dp[i][j] && j - i + 1 >= maxLen){
                        maxLen = j - i + 1;
                        start = i;
                        end = j;
                }
            }
        }
        return s.substr(start,end - start + 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
25
26
27
28
29

13 最长回文子序列

1. 确定dp数组（dp table）以及下标的含义

dp[i][j]：字符串s在[i, j]范围内最长的回文子序列的长度为dp[i][j]。

2. 确定递推公式

如果s[i]与s[j]相同，那么dp[i][j] = dp[i + 1][j - 1] + 2;

如果不相等则取两端部分的最大值分别加入s[i]、s[j]看看哪一个可以组成最长的回文子序列。

dp[i][j] = max(dp[i + 1][j], dp[i][j - 1]);

3. 初始化

根据定义 i -> i为1， 初始化为0

4. 遍历顺序

和之前一样，防止dp[i+1][j-1]被覆盖，同时要考虑dp[i+1][j]

需要注意的是由于dp[i+1][j] 所以j+1开始遍历

class Solution {
public:
    int longestPalindromeSubseq(string s) {
        int n = s.size();
        if(n <= 1){
            return n;
        }
        // dp[i][j] 表示[i][j]的最长回文子序列的长度
        vector<vector<int>> dp(n+1, vector<int>(n+1,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];
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

总结