八、动态规划（Dynamic Programming）

一、理论基础

动态规划，英文：Dynamic Programming，简称DP，如果某一问题有很多重叠子问题，使用动态规划是最有效的。
所以动态规划中每一个状态一定是由上一个状态推导出来的，这一点就区分于贪心，贪心没有状态推导，而是从局部直接选最优的！
对于动态规划问题，拆解为如下五步曲，这五步都搞清楚了，才能说把动态规划真的掌握了！

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

做动规的题目，写代码之前一定要把状态转移在dp数组的上具体情况模拟一遍，心中有数，确定最后推出的是想要的结果。

二、题目分类

（一）基础题目

2.70.爬楼梯

（1）思路

1. 确定dp数组以及下标的含义
   dp[i]： 爬到第i层楼梯，有dp[i]种方法

2. 确定递推公式
   如何可以推出dp[i]呢？
   从dp[i]的定义可以看出，dp[i] 可以有两个方向推出来。
   首先是dp[i - 1]，上i-1层楼梯，有dp[i - 1]种方法，那么再一步跳一个台阶不就是dp[i]了么。
   还有就是dp[i - 2]，上i-2层楼梯，有dp[i - 2]种方法，那么再一步跳两个台阶不就是dp[i]了么。
   那么dp[i]就是 dp[i - 1]与dp[i - 2]之和！
   所以dp[i] = dp[i - 1] + dp[i - 2] 。
   在推导dp[i]的时候，一定要时刻想着dp[i]的定义，否则容易跑偏。

这体现出确定dp数组以及下标的含义的重要性！

3. dp数组如何初始化
   再回顾一下dp[i]的定义：爬到第i层楼梯，有dp[i]种方法。
   那么i为0，dp[i]应该是多少呢，这个可以有很多解释，但基本都是直接奔着答案去解释的。

例如强行安慰自己爬到第0层，也有一种方法，什么都不做也就是一种方法即：dp[0] = 1，相当于直接站在楼顶。
但总有点牵强的成分。

那还这么理解呢：我就认为跑到第0层，方法就是0啊，一步只能走一个台阶或者两个台阶，然而楼层是0，直接站楼顶上了，就是不用方法，dp[0]就应该是0.

其实这么争论下去没有意义，大部分解释说dp[0]应该为1的理由其实是因为dp[0]=1的话在递推的过程中i从2开始遍历本题就能过，然后就往结果上靠去解释dp[0] = 1。

从dp数组定义的角度上来说，dp[0] = 0 也能说得通。

需要注意的是：题目中说了n是一个正整数，题目根本就没说n有为0的情况。

所以本题其实就不应该讨论dp[0]的初始化！

我相信dp[1] = 1，dp[2] = 2，这个初始化大家应该都没有争议的。
所以我的原则是：不考虑dp[0]如何初始化，只初始化dp[1] = 1，dp[2] = 2，然后从i = 3开始递推，这样才符合dp[i]的定义。

4. 确定遍历顺序
   从递推公式dp[i] = dp[i - 1] + dp[i - 2];中可以看出，遍历顺序一定是从前向后遍历的

5. 举例推导dp数组
   举例当n为5的时候，dp table（dp数组）应该是这样的

（2）代码

版本一：
class Solution {
public:
    int climbStairs(int n) {
    if(n <= 1)
    return 1;
    vector<int> dp(n + 1);
	dp[1] = 1;
	dp[2] = 2;
	for (int i = 3; 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
14
15

// 版本二
class Solution {
public:
    int climbStairs(int n) {
        if (n <= 1) return n;
        int dp[3];
        dp[1] = 1;
        dp[2] = 2;
        for (int i = 3; i <= n; i++) {
            int sum = dp[1] + dp[2];
            dp[1] = dp[2];
            dp[2] = sum;
        }
        return dp[2];
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

（3）复杂度分析

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

3.746. 使用最小花费爬楼梯

（1）思路

1. 确定dp数组以及下标的含义
   dp[i]的定义：到达第i台阶所花费的最少体力为dp[i]。
2. 可以有两个途径得到dp[i]，一个是dp[i-1] 一个是dp[i-2]， 所以dp[i] = min(dp[i - 1] + cost[i - 1], dp[i - 2] + cost[i - 2]);
3. dp数组如何初始化
   所以初始化 dp[0] = 0，dp[1] = 0;
4. 确定遍历顺序
   最后一步，递归公式有了，初始化有了，如何遍历呢？
   本题的遍历顺序其实比较简单，简单到很多同学都忽略了思考这一步直接就把代码写出来了。
   因为是模拟台阶，而且dp[i]由dp[i-1]dp[i-2]推出，所以是从前到后遍历cost数组就可以了。
5. 举例推导dp数组
   示例2：cost = [1, 100, 1, 1, 1, 100, 1, 1, 100, 1] ，来模拟一下dp数组的状态变化，如下：

（2）代码

class Solution {
public:
    int minCostClimbingStairs(vector<int>& cost) {
        vector<int> dp(cost.size() + 1);
        dp[0] = 0; // 默认第一步都是不花费体力的
        dp[1] = 0;
        for (int i = 2; i <= cost.size(); i++) {
            dp[i] = min(dp[i - 1] + cost[i - 1], dp[i - 2] + cost[i - 2]);
        }
        return dp[cost.size()];
    }
};
1
2
3
4
5
6
7
8
9
10
11
12

（3）复杂度分析

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

4.62.不同路径

（1）思路

（2）代码

class Solution {
public:

    int uniquePaths(int m, int n) {
        vector<vector<int>> dp(m + 1,vector<int>(n + 1));
        // 1. 含义：到第m行n列共有几条路。
        // 2. 公式：dp[i - 1][j] + dp[i][j - 1]
        // 3. 初始化：  for j in n dp[0][j] = 1;   for i in m dp[i][0] = 1;  
        // 4. 方向：从前向后 
        // 5. 打印：
        dp[0][0] = 1;
        for (int j = 1; j < n; j++) {
            dp[0][j] = 1;
        }
        for (int i = 1; i < m; i++) {
            dp[i][0] = 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
15
16
17
18
19
20
21
22
23
24
25

（3）复杂度分析

时间复杂度：$O(m\times n)$
空间复杂度：$O(n)$

5.63.不同路径2

（1）思路

// 1. 含义：到第m行n列共有几条路。
// 2. 公式：dp[i - 1][j] + dp[i][j - 1]
// 3. 初始化： for j in n dp[0][j] = 1; for i in m dp[i][0] = 1; // 注意代码里for循环的终止条件，一旦遇到obstacleGrid[i][0] == 1的情况就停止dp[i][0]的赋值1的操作，dp[0][j]同理
// 4. 方向：从前向后
// 5. 打印：

（2）代码

class Solution {
public:
    int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {
        int m = obstacleGrid.size();
        int n = obstacleGrid[0].size();
        vector<vector<int>> dp(m + 1,vector<int>(n + 1));
        if (obstacleGrid[m - 1][n - 1] == 1 || obstacleGrid[0][0] == 1) //如果在起点或终点出现了障碍，直接返回0
            return 0;
        // 1. 含义：到第m行n列共有几条路。
        // 2. 公式：dp[i - 1][j] + dp[i][j - 1]
        // 3. 初始化：  for j in n dp[0][j] = 1;   for i in m dp[i][0] = 1;  
        // 4. 方向：从前向后 
        // 5. 打印：
        dp[0][0] = 1;
        for (int j = 1; j < n && obstacleGrid[0][j] == 0; j++) { // 注意代码里for循环的终止条件，一旦遇到obstacleGrid[i][0] == 1的情况就停止dp[i][0]的赋值1的操作，dp[0][j]同理
            dp[0][j] = 1;
        }
        for (int i = 1; i < m && obstacleGrid[i][0] == 0; i++) {
            dp[i][0] = 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
18
19
20
21
22
23
24
25
26
27
28
29

（3）复杂度分析

时间复杂度：$O(m\times n)$
空间复杂度：$O(n)$

6.343.整数拆分

（1）思路

看到这道题目，都会想拆成两个呢，还是三个呢，还是四个…

我们来看一下如何使用动规来解决。

（2）代码

class Solution {
public:
    int integerBreak(int n) {
    // 1.确定dp数组（dp table）以及下标的含义 dp[i]：分拆数字i，可以得到的最大乘积为dp[i]。
    // 2.公式：一个是j * (i - j) 直接相乘。一个是j * dp[i - j]，相当于是拆分(i - j)。
    // 3.dp的初始化 只初始化dp[2] = 1
    // 4.dp[i] = max(dp[i], max((i - j) * j, dp[i - j] * j));
    // 5.
        vector<int> dp(n + 1);
        dp[2] = 1;
        for (int i = 3; i <= n ; i++) {
            for (int j = 1; j <= i / 2; 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
14
15
16
17
18

贪心：
class Solution {
public:
    int integerBreak(int n) {
        if (n == 2) return 1;
        if (n == 3) return 2;
        if (n == 4) return 4;
        int result = 1;
        while (n > 4) {
            result *= 3;
            n -= 3;
        }
        result *= n;
        return result;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

（3）复杂度分析

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

（二）背包问题-01背包

有n件物品和一个最多能背重量为w 的背包。第i件物品的重量是weight[i]，得到的价值是value[i] 。每件物品只能用一次，求解将哪些物品装入背包里物品价值总和最大。

二维dp数组01背包
依然动规五部曲分析一波。

1. 确定dp数组以及下标的含义
   对于背包问题，有一种写法， 是使用二维数组，即dp[i][j] 表示从下标为[0-i]的物品里任意取，放进容量为j的背包，价值总和最大是多少。
2. 确定递推公式
   再回顾一下dp[i][j]的含义：从下标为[0-i]的物品里任意取，放进容量为j的背包，价值总和最大是多少。

那么可以有两个方向推出来dp[i][j]，

• 不放物品i：由dp[i - 1][j]推出，即背包容量为j，里面不放物品i的最大价值，此时dp[i][j]就是dp[i - 1][j]。(其实就是当物品i的重量大于背包j的重量时，物品i无法放进背包中，所以背包内的价值依然和前面相同。)
• 放物品i：由dp[i - 1][j - weight[i]]推出，dp[i - 1][j - weight[i]] 为背包容量为j - weight[i]的时候不放物品i的最大价值，那么dp[i - 1][j - weight[i]] + value[i] （物品i的价值），就是背包放物品i得到的最大价值
  所以递归公式： dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]);

3. dp数组如何初始化
   关于初始化，一定要和dp数组的定义吻合，否则到递推公式的时候就会越来越乱。

首先从dp[i][j]的定义出发，如果背包容量j为0的话，即dp[i][0]，无论是选取哪些物品，背包价值总和一定为0。如图：

1.416.分割等和子集

class Solution {
public:
    bool canPartition(vector<int>& nums) {
    	vector<int> dp(10001,0);
    	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;
		return false;
    }
} 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

2.1049. 最后一块石头的重量 II

class Solution {
public:
    int lastStoneWeightII(vector<int>& stones) {
    // 1.确定dp数组以及下标的含义 dp[j]表示容量（这里说容量更形象，其实就是重量）为j的背包，最多可以背最大重量为dp[j]。
    // 2.dp[j] = max(dp[j], dp[j - stones[i]] + stones[i]);
    // 3.dp数组如何初始化 
    // 4.如果使用一维dp数组，物品遍历的for循环放在外层，遍历背包的for循环放在内层，且内层for循环倒序遍历！
    // 5.
        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
16
17
18
19
20

（三）背包问题-完全背包

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

完全背包和01背包问题唯一不同的地方就是，每种物品有无限件。

// 先遍历物品，再遍历背包
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]);

    }
}
1
2
3
4
5
6
7

1.518. 零钱兑换 II

class Solution {
public:
    int change(int amount, vector<int>& coins) {
    // 1.dp[j]：凑成总金额j的货币组合数为dp[j]
    // 2.确定递推公式 dp[j] 就是所有的dp[j - coins[i]]（考虑coins[i]的情况）相加。
    // 3.dp数组如何初始化 首先dp[0]一定要为1，dp[0] = 1是 递归公式的基础。如果dp[0] = 0 的话，后面所有推导出来的值都是0了。
        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
14
15
16

2.377. 组合总和 Ⅳ

class Solution {
public:
    int combinationSum4(vector<int>& nums, int target) {
        // 组合不强调顺序，(1,5)和(5,1)是同一个组合。
        // 排列强调顺序，(1,5)和(5,1)是两个不同的排列。
        // 1. dp[i]表示凑成目标正整数为i的排列个数为dp[i];
        // 2. dp[i] += dp[i - nums[i]];
        // 3. dp[0] = 1;
        vector<int> dp (target + 1,0);
        dp[0] = 1;
        for (int i = 0; i <= target; i++) { // 背包
            for (int j = 0; j < nums.size(); 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
20

3.322. 零钱兑换

class Solution {
public:
    int coinChange(vector<int>& coins, int amount) {
        vector<int> dp(amount + 1, INT_MAX);
        dp[0] = 0;
        for (int i = 0; i < coins.size(); i++) { // 遍历物品
            for (int j = coins[i]; j <= amount; j++) { // 遍历背包
                if (dp[j - coins[i]] != INT_MAX) { // 如果dp[j - coins[i]]是初始值则跳过
                    dp[j] = min(dp[j - coins[i]] + 1, dp[j]);
                }
            }
        }
        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

4.279. 完全平方数

class Solution {
public:
    int numSquares(int n) {
    // 1. 含义: 和为 j 的完全平方数的最少数量为 dp[j]
    // 2. 公式：dp[j] = min(dp[j - i * i] + 1, dp[j]);
    // 3. 初始化：dp[0] = 1;
    // 4. 顺序
    // 5. 验证
        vector<int> dp(n + 1, INT_MAX);
        dp[0] = 0;
        for (int i = 1; i * i <= n; i++) {  // 遍历物品
            for (int j = i * i; j <= n; j++) { // 遍历背包
                dp[j] = min(dp[j - i * i] + 1, dp[j]);
            }
        }
        return dp[n];
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

（四）打家劫舍

（五）股票

（六）子序列

1. 300.最长递增子序列

（1）思路

1. dp[i]的定义
   本题中，正确定义dp数组的含义十分重要。

dp[i]示i之前包括i的以nums[i]结尾的最长递增子序列的长度
为什么一定表示 “以nums[i]结尾的最长递增子序” ，因为我们在 做 递增比较的时候，如果比较 nums[j] 和 nums[i] 的大小，那么两个递增子序列一定分别以nums[j]为结尾和 nums[i]为结尾， 要不然这个比较就没有意义了，不是尾部元素的比较那么如何算递增呢。

2. 状态转移方程
   位置i的最长升序子序列等于j从0到i-1各个位置的最长升序子序列 + 1 的最大值。

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

注意这里不是要dp[i] 与 dp[j] + 1进行比较，而是我们要取dp[j] + 1的最大值。

3. dp[i]的初始化
   每一个i，对应的dp[i]（即最长递增子序列）起始大小至少都是1.

4. 确定遍历顺序
   dp[i] 是有0到i-1各个位置的最长递增子序列 推导而来，那么遍历i一定是从前向后遍历。

j其实就是遍历0到i-1，那么是从前到后，还是从后到前遍历都无所谓，只要吧 0 到 i-1 的元素都遍历了就行了。 所以默认习惯 从前向后遍历。

5. 举例推导

（2）代码

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
16

（3）复杂度分析

时间复杂度: $O(n^2)$
空间复杂度: $O(n)$

2. 674. 最长连续递增序列

（1）思路

1. 确定dp数组（dp table）以及下标的含义，dp[i]：以下标i为结尾的连续递增的子序列长度为dp[i]。
2. 确定递推公式
   如果 nums[i] > nums[i - 1]，那么以 i 为结尾的连续递增的子序列长度 一定等于 以i - 1为结尾的连续递增的子序列长度 + 1 。即：dp[i] = dp[i - 1] + 1;因为本题要求连续递增子序列，所以就只要比较nums[i]与nums[i - 1]，而不用去比较nums[j]与nums[i] （j是在0到i之间遍历）。
3. 确定递推公式 以下标i为结尾的连续递增的子序列长度最少也应该是1，即就是nums[i]这一个元素。
4. 确定遍历顺序
   从递推公式上可以看出， dp[i + 1]依赖dp[i]，所以一定是从前向后遍历。
5. 举例推导dp数组
   已输入nums = [1,3,5,4,7]为例，dp数组状态如下：

（2）代码

class Solution {
public:
    int findLengthOfLCIS(vector<int>& nums) {
        // 1. dp[i]的定义，以i结尾的最长连续递增子序列长度
        // 2. 方程  if (nums[i] > nums[i - 1]) dp[i] = dp[i - 1] + 1;
        // 3. 初始  dp[0] = 1; 
        // 4. 顺序  从左到右
        // 5. 打印 
        if (nums.size() == 0) return 0;
        int result = 1;
        vector<int> dp(nums.size() ,1);
        for (int i = 1; i < nums.size(); i++) {
            if (nums[i] > nums[i - 1]) { // 连续记录
                dp[i] = dp[i - 1] + 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
16
17
18
19
20
21

（3）复杂度分析

时间复杂度: $O(n)$
空间复杂度: $O(n)$

3. 18. 最长重复子数组

（1）思路

// 1. dp[i][j] 表示，nums1以i - 1结尾，nums2以j - 1结尾的最长重复子数组的长度
// 2. 方程：根据dp[i][j]的定义，dp[i][j]的状态只能由dp[i - 1][j - 1]推导出来。
即当A[i - 1] 和B[j - 1]相等的时候，dp[i][j] = dp[i - 1][j - 1] + 1;
根据递推公式可以看出，遍历i 和 j 要从1开始！ dp[i][j] = dp[i - 1][j - 1] + 1;
// 3. 初始化 所以dp[i][0] 和dp[0][j]初始化为0。
// 4. 顺序 外层for循环遍历A，内层for循环遍历B。
// 5. 打印

（2）代码

class Solution {
public:
    int findLength(vector<int>& nums1, vector<int>& nums2) {
        // 1. dp[i][j] 表示，nums1以i - 1结尾，nums2以j - 1结尾的最长重复子数组的长度
        // 2. 方程： dp[i][j] = dp[i - 1][j - 1] + 1;
        // 3. 初始化 所以dp[i][0] 和dp[0][j]初始化为0。
        // 4. 顺序 外层for循环遍历A，内层for循环遍历B。
        // 5. 打印
        vector<vector<int>> dp (nums1.size() + 1, vector<int>(nums2.size() + 1, 0));
        int result = 0;
        for (int i = 1; i <= nums1.size(); i++) {
            for (int j = 1; j <= nums2.size(); j++) {
                if (nums1[i - 1] == nums2[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
17
18
19
20
21

4. 1143. 最长公共子序列

（3）复杂度分析

时间复杂度: $O(n\ast m)$
空间复杂度: $O(n\ast m)$

（1）思路

// 1. dp[i][j] 表示，长度为[0, i - 1]的字符串text1与长度为[0, j - 1]的字符串text2的最长公共子序列为dp[i][j]
// 2. 方程： if (text1[i] == text2[j]) dp[i][j] = dp[i - 1][j - 1] + 1;
// else dp[i][j] = max(dp[i - 1][j],dp[i][j - 1])
// 3. 初始化 if (text1[0] == text2[0]) dp[0][0] = 1; else dp[0][0] = 0;
// 4. 顺序 外层for循环遍历A，内层for循环遍历B。
// 5. 打印

（2）代码

class Solution {
public:
    int longestCommonSubsequence(string text1, string text2) {
        // 1. dp[i][j] 表示，长度为[0, i - 1]的字符串text1与长度为[0, j - 1]的字符串text2的最长公共子序列为dp[i][j]
        // 2. 方程： if (text1[i] == text2[j]) dp[i][j] = dp[i - 1][j - 1] + 1;
             // else dp[i][j] = max(dp[i - 1][j],dp[i][j - 1])
        // 3. 初始化 if (text1[0] == text2[0]) dp[0][0] = 1; else dp[0][0] = 0;
        // 4. 顺序 外层for循环遍历A，内层for循环遍历B。
        // 5. 打印
        vector<vector<int>> dp(text1.size() + 1,vector<int>(text2.size() + 1, 0));
        for (int i = 1; i <= text1.size(); i++) {
            for (int j = 1; j <= text2.size(); 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]);
                }
            }
        }
          return dp[text1.size()][text2.size()];
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

（3）复杂度分析

时间复杂度: $O(n\ast m)$
空间复杂度: $O(n\ast m)$

5. 1035.不相交的线

（1）思路

和1143. 最长公共子序列思路一样！

（2）代码

class Solution {
public:
    int maxUncrossedLines(vector<int>& nums1, vector<int>& nums2) {
        // 1. dp[i][j]  nums1以i 结尾 nums2 以j结尾的最长公共子序列的长度！
         vector<vector<int>> dp(nums1.size() + 1, vector<int>(nums2.size() + 1, 0));
        for (int i = 1; i <= nums1.size(); i++) {
            for (int j = 1; j <= nums2.size(); 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]);
                }
            }
        }
        return dp[nums1.size()][nums2.size()];
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

（3）复杂度分析

时间复杂度: $O(n\ast m)$
空间复杂度: $O(n\ast m)$

6. 53.最大子数组和

（1）思路

   // 1. dp[i] 包括下标i（以nums[i]为结尾）的最大连续子序列和为dp[i]
    // 2. dp[i] = max(nums[i],dp[i - 1] + nums[i]);  dp[i - 1] + nums[i]，即：nums[i]加入当前连续子序列和
    // nums[i]，即：从头开始计算当前连续子序列和
    // 3.  从递推公式可以看出来dp[i]是依赖于dp[i - 1]的状态，dp[0]就是递推公式的基础。
    // 4. 1 - n
    // 5. 方程
1
2
3
4
5
6

（2）代码

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        // 1. dp[i] 包括下标i（以nums[i]为结尾）的最大连续子序列和为dp[i]
        // 2. dp[i] = max(nums[i],dp[i - 1] + nums[i]);  dp[i - 1] + nums[i]，即：nums[i]加入当前连续子序列和
        // nums[i]，即：从头开始计算当前连续子序列和
        // 3.  从递推公式可以看出来dp[i]是依赖于dp[i - 1]的状态，dp[0]就是递推公式的基础。
        // 4. 1 - n
        // 5. 方程
        if (nums.size() == 0) return 0;
     
        vector<int> dp(nums.size(),0);
        
        dp[0] = nums[0];
        int result = dp[0];
        for (int i = 1; i < nums.size(); i++) {
            dp[i] = max(dp[i - 1] + nums[i],nums[i]);
            if (dp[i] > result) result = dp[i];
        }
        return result;
    } 
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

（3）复杂度分析

时间复杂度: $O(n)$
空间复杂度: $O(n)$

7. 392. 判断子序列

（1）思路

1. 确定dp数组（dp table）以及下标的含义
   dp[i][j] 表示以下标i-1为结尾的字符串s，和以下标j-1为结尾的字符串t，相同子序列的长度为dp[i][j]。
2. 确定递推公式
   在确定递推公式的时候，首先要考虑如下两种操作，整理如下：
   if (s[i - 1] == t[j - 1])
   t中找到了一个字符在s中也出现了
   if (s[i - 1] != t[j - 1])
   相当于t要删除元素，继续匹配
3. dp数组如何初始化
   从递推公式可以看出dp[i][j]都是依赖于dp[i - 1][j - 1] 和 dp[i][j - 1]，所以dp[0][0]和dp[i][0]是一定要初始化的。
4. 确定遍历顺序
   同理从递推公式可以看出dp[i][j]都是依赖于dp[i - 1][j - 1] 和 dp[i][j - 1]，那么遍历顺序也应该是从上到下，从左到右
5. 举例推导dp数组

（2）代码

class Solution {
public:
    bool isSubsequence(string s, string t) {
        // 1. dp[i][j] 表示 s 以 i - 1 结尾，t 以 j - 1 结尾， 相同子序列的长度为dp[i][j]
        // 2. if (s[i - 1] == t[j - 1])，那么dp[i][j] = dp[i - 1][j - 1] + 1;，因为找到了一个相同的字符，相同子序列长度自然要在dp[i-1][j-1]的基础上加1
        // if (s[i - 1] != t[j - 1])，此时相当于t要删除元素，t如果把当前元素t[j - 1]删除，那么dp[i][j] 的数值就是 看s[i - 1]与 t[j - 2]的比较结果了，即：dp[i][j] = dp[i][j - 1];
        // 3. 初始化
        // 4. 同理从递推公式可以看出dp[i][j]都是依赖于dp[i - 1][j - 1] 和 dp[i][j - 1]，那么遍历顺序也应该是从上到下，从左到右
        vector<vector<int>> dp(s.size() + 1, vector<int>(t.size() + 1, 0));
         for (int i = 1; i <= s.size(); i++) {
            for (int j = 1; j <= t.size(); j++) {
                if (s[i - 1] == t[j - 1]) dp[i][j] = dp[i - 1][j - 1] + 1;
                else dp[i][j] = dp[i][j - 1];
            }
        }
       if (dp[s.size()][t.size()] == s.size()) return true;
        return false;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

（3）复杂度分析

时间复杂度: $O(n\ast m)$
空间复杂度: $O(n\ast m)$

8. 115. 不同的子序列

（1）思路

1. 确定dp数组（dp table）以及下标的含义
   dp[i][j]：以i-1为结尾的s子序列中出现以j-1为结尾的t的个数为dp[i][j]。
2. 确定递推公式
   这一类问题，基本是要分析两种情况
   s[i - 1] 与 t[j - 1]相等
   s[i - 1] 与 t[j - 1] 不相等

（2）代码

（3）复杂度分析

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

（1）思路

（2）代码

（3）复杂度分析

10.72. 编辑距离

（1）思路

（2）代码

（3）复杂度分析

11.647. 回文子串

（1）思路

1. 布尔类型的dp[i][j]：表示区间范围[i,j] （注意是左闭右闭）的子串是否是回文子串，如果是dp[i][j]为true，否则为false。
2. 公式：
   当s[i]与s[j]不相等，那没啥好说的了，dp[i][j]一定是false。
   当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。

3. dp[i][j]可以初始化为true么？ 当然不行，怎能刚开始就全都匹配上了。
   所以dp[i][j]初始化为false。
4. 确定遍历顺序
   所以一定要从下到上，从左到右遍历，这样保证dp[i + 1][j - 1]都是经过计算的。
5. 举例推导dp数组

（2）代码

（3）复杂度分析

12.516. 最长回文子序列

（1）思路

（2）代码

（3）复杂度分析