Leetcode动态规划篇总结（C++）_leetcode c++ 动态规划

注：按照代码随想录的刷题指南进行，自己总结补充，以加深印象
参考链接：https://leetcode-cn.com/circle/article/wGp7Y9/
题目来源：力扣（LeetCode）

一、基础知识

1、动态规划思想

动态规划中每一个状态一定是由前面的状态推导出来的
dp数组存储的是可维持的状态，而递推公式是达到该状态的动作

2、解题步骤（有用！）

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

3、背包问题

3.1 01背包

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

• 每个物品都有取或者不取两种选择，则可以用回溯法暴力搜索，但时间是指数级别的复杂度,容易超时。
  二维数组写法 ：

1. dp[i][j] 表示从下标为[0-i]的物品里任意取，放进容量为j的背包，价值总和最大是多少
2. 递推公式：两个方向，取与不取：
   不取物品：j < weight[i], 则dp[i][j] = dp[i-1][j]
   取物品： j >= weight[i], 则dp[i][j] = dp[i - 1][j - weight[i]] + value[i]

所以公式为：dp[i][j] = max{ dp[i-1][j], dp[i - 1][j - weight[i]] + value[i]}

3. 初始化
   如果背包容量j为0的话，即dp[i][0]，无论是选取哪些物品，背包价值总和一定为0。
   dp[0][j]，即：i为0，存放编号0的物品的时候，各个容量的背包所能存放的最大价值。(j >= weight[0], dp[0][j] = value[0] ; 否则为0）

一般可以把数组全部初始化为0， 方便

4. 遍历顺序
   物品和背包容量的遍历顺序不限。（可以从递归公式的方向来看）
5. 举例

滚动数组写法（一维）
1.dp[j]表示容量为j的背包，可存放的物品的最大价值
2. 递推公式：

dp[j] = max{ dp[j], dp[j - weight[i]] + value[i]}

3.初始化：注意dp[j]代表的是容量，需要计算一下最大容量的上线
4.遍历顺序！！先物品再容量，内层循环倒序是为了用上一个状态的数值，正序的话会状态会被更新

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]);
		}
    }
1
2
3
4
5

3.2 完全背包

与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]);

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

3.3 多重背包

• 问题：有N种物品和一个容量为V 的背包。第i种物品最多有Mi件可用，每件耗费的空间是Ci ，价值是Wi 。求解将哪些物品装入背包可使这些物品的耗费的空间 总和不超过背包容量，且价值总和最大。
• 和01背包很像，把M件摊开，就是一个01背包问题了,即扩充物品数组
• 第二种解决办法是把每种商品遍历的个数放在01背包里再遍历一遍

for(int i = 0; i < weight.size(); i++){//遍历物品
	for(int j = bagWeight; j >= weight[i]; j--){//遍历容量
		for(int k = 1; k < = nums[i]; k++){
			dp[j] = max(dp[j], dp[j - weight[i]*k] + value[i]*k);
		}
	}
}

1
2
3
4
5
6
7
8

• 多重背包在面试中基本不会出现，力扣上也没有对应的题目，大家对多重背包的掌握程度知道它是一种01背包，并能在01背包的基础上写出对应代码就可以了。

背包相关问题

1、比如面试题，要求先用二维dp数组实现，然后再用一维dp数组实现（），最后在问，两个for循环的先后是否可以颠倒？为什么？

2、求组合数的背包，递推公式怎么推？
不考虑nums[i]的情况下，填满容量为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]]

3、

如果求组合数就是外层for循环遍历物品，内层for遍历背包。(即保证物品的放入顺序） 518题

理由：来自官方解答

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

理由：来自官方解答

4、
leetcode上没有纯01/完全背包的问题，都是应用方面的题目，也就是需要转化为背包问题，转换的思路是最关键的

5、背包套路总结
https://github.com/youngyangyang04/leetcode-master/blob/master/problems/%E8%83%8C%E5%8C%85%E6%80%BB%E7%BB%93%E7%AF%87.md

4、打家劫舍问题

小偷也要有文化，看题

5、股票买卖问题(动规本质）

• 股票买卖问题牵扯到一个物品有多状态，后续递推公式会根据情况参考以往的某个状态计算。之前做背包问题形成了固定思维，只知道带入框架，这里才有点明白动规的真正意义：我要记录一个事务之前的状态去方便后续的计算（但这不代表过去的状态只有一个）。
• 比如背包问题，可以理解为背包在物品i阶段的状态，有0-capacity这些状态。而股票买卖，是在第i天，自己钱包的两个状态：持股和不持股。所以一些文章写买入状态和卖出状态是不准确的，dp数组存储的是可维持的状态，而递推公式是达到该状态的动作。比如今天达到持股状态有两种途径，一个是维持前一天的持股状态，一个是今天买入股票，所以公式dp[i][0] = max(dp[i - 1][0], dp[i-1][1] - prices[i])

6、子序列问题

• 注意的一点是可能需要在dp矩阵前添加一行和一列，方便边界情况的计算，俗称哨兵思想，比如lcp问题
• 子串（substring）,连续
  子序列(subsequece),可不连续

二、经典题目

基础问题

1、509-斐波那契数列-简单

• 题目链接
• 经典题目，没什么好说的，一种迭代法，一种递归法。可以不用看。
• 这里主要可以提的是一个内存优化，即将dp数组值保存两个元素，不断更新,最后返回dp[n]，但显然无法保存中间结果，不适合多输入的情况。

2、70-爬楼梯-简单 + 746进阶版

• 题目链接
• 分析方法：第一层1种，第二层两种，第三层楼梯的状态可以由第二层楼梯 和 到第一层楼梯状态推导出来，那么就可以想到动态规划了
• 本质上还是上题，主要是你对dp的理解：此处dp[i]代表到达第i层的方法数
• 方法2：完全背包问题解法
• 扩展：一步一个台阶，两个台阶，三个台阶，直到 m个台阶，有多少种方法爬到n阶楼顶。（代码随想录上有答案）
• 进阶版：746-使用最小花费爬楼梯-简单。并无复杂逻辑，明确dp代表什么即可 题目链接

3、62-不同路径-中等 + 63进阶版

• 题目链接
• 机器人走格子，相比于前两道题，动态规划的矩阵从一维变为二维，但本质未变
• 62有两种解题思想，一个动规，一个组合数学（其中要注意计算过程的溢出问题）
• 二维动态矩阵的内存优化：用一个一维数组（滚动数组）表示一行
• 进阶版：无复杂逻辑，题目链接

4、343-整数拆分-中等 + 96-不同的二叉搜索树-中等

• 343 题目链接
• 96 题目链接
• l两者难点都在公式推导上，而且其推导公式需要前面所有的状态，所以推导公式的方法是什么？找规律？
• 整数拆分还有一种通过数学公式求解的方法，只能说数学的力量无穷。

01背包问题

416-分割等和子集-中等

• 问一个数组能否划分为数值和相等两个子集 ， 题目链接
• 每个子集的和必须达到ave,每个元素取一次，01背包问题
• 如何转化为01背包问题？（关键点）
  本题中物品是nums[i]，重量是nums[i]，价值也是nums[i]，背包体积是sum/2。
• dp[i]代表背包容量为i时的最大数值和
• 结果如何判断？
  最后的target = sum/2, 我只需要判断dp[target] 是否等于target就可以了

1049. 最后一块石头的重量 II-中等

• 取数组里的两块石头放在一起粉碎（即两数相减），不断重复，最终留下的最小的重量 题目链接
• 关键点：如何转化为01背包问题？
  本题其实就是尽量让石头分成重量相同的两堆，相撞之后剩下的石头最小，这样就化解成01背包问题了，变成了分割等和子集的题目
• dp[j]为容量为j的时候，最多可以背dp[j]这么重的石头
• 结果判断条件？
  最后dp[target]里是容量为target的背包所能背的最大重量。那么分成两堆石头，一堆石头的总重量是dp[target]，另一堆就是sum - dp[target]。target = sum / 2 因为是向下取整，那么相撞之后剩下的最小石头重量就是 (sum - dp[target]) - dp[target]。

本题其实和416. 分割等和子集几乎是一样的，只是最后对dp[target]的处理方式不同。
416. 分割等和子集相当于是求背包是否正好装满，而本题是求背包最多能装多少。

494-目标和-中等

• 在数组的每个元素前加+或者-号，使最后的表达式值为target ， 问有几种方法 题目链接
• 写出来了回溯法，但没写出动规
• 如何转化为01背包问题？
  假设数组元素总和为sum, 加法总和为x， 用于减法的元素总和就是sum-x, 我们要求的是x - (sum-x) = s, x = (s+sum)/2，此时问题转化为装满容量为x的背包，需要几种方法
• dp[j]表示容量为j时，填满j的背包有dp[j]种方法（这是一个一个组合问题,上面两个是最多能装多少的问题）

在求装满背包有几种方法的情况下，递推公式一般为：
dp[j] += dp[j - nums[i]] （相当于一个矩阵的同一列加起来）

474-一和零-中等

• 一个有01组成的字符串数组， 返回m个0和n个1的字符串组合的最大数量题目链接
• 如何转换为01背包问题
  一个元素取一次，是01背包问题，只是背包有两个维度。假设当前字符str有a个0， b个1，此时a和b相当于重量，字符串本身的个数相当于物品价值
• dp[i][j]代表i个0j个1时的字符串数量
• dp[i][j] = max(dp[i-a][j-b] + 1, dp[i][j])
• 内层两个维度的顺序无碍
• 时间复杂度O(kmn + L),k为字符串数目,L为数组内所有字符串长度（因为需要遍历字符串统计01字符）

完全背包问题

518-零钱兑换II-中等（组合）

• 一个零钱数组，每个元素可以取任意个，问恰好取amount的方法有几个题目链接
• 完全背包问题，但要注意结果是组合数，递推公式为dp[j] += dp[j- coins[i];
• 因为是求的组合，所以一定是先遍历物品，再遍历容量（保证不会同时出现0 1 2 和 2 1 0 的情况）。反过来，下面的一题则是先容量再物品。

377-组合总和IV- 中等（排列）

• 上题的排列版本，题目链接

• 注意两个关键问题：

  • 递推公式的由来？
  • 排列和组合的遍历顺序不同，为什么？

322-零钱兑换-中等 + 279-完全平方数-中等

• 零钱可以无限取，问组合为amount的最小硬币数题目链接
• 完全背包，但是问最少硬币个数，不追求顺序
• dp[j] 表示容量为j时的最小硬币数目
• dp[j] = min{dp[j - coinsp[i]] + 1, dp[j]}
• 组合成0的硬币个数为0，所以dp[0] = 0;因为时取较小值，所以其余声明为int_max,注意为了防止溢出，要额外判断
• 不追求顺序，所以遍历顺序无关
• 279题与零钱兑换一个套路，只不过是多生成一个完全平方数数组罢了

139-单词拆分-中等（记忆化搜索）

• 给你一个字符串 s 和一个字符串列表 wordDict 作为字典。请你判断是否可以利用字典中出现的单词拼接出 s 。不要求字典中出现的单词全部都使用，并且字典中的单词可以重复使用 题目链接
• 这道题做了很久，判断是完全背包，但dp[i]一直想的是代表0-i的字符串的相似度，推不出公式。后来改用回溯，对单词数组进行组合，但overstack ,
• 完全背包法，dp[j]为长度为j的字符串,dp[j]为true, 表示符合条件
  • dp[j]为true，且 [j,i]的这个区间的字串出现在字典里，那么dp[i]为true
  • dp[0] = true
  • 因为只是问是否可以，所以组合排列都可。但是外层遍历物品，需要把所有字串提前放在一个容器里，所以最好是外层容量
• 回溯法：感觉应该算是递归，不能称为回溯，没有状态的还原。核心思想是枚举分割所有的字符串，判断字串是否在字典里出现过
• 有一个优化是记忆化搜索，即通过数组保存一下递归过程中计算的结果，避免重复计算。

打家劫舍问题

198-打家劫舍-中等

• 给定一个代表每个房屋存放金额的非负整数数组，计算你 不触动警报装置(连续偷相邻房间会报警）的情况下 ，一夜之内能够偷窃到的最高金额题目链接
• dp[i]：考虑下标i（包括i）以内的房屋，最多可以偷窃的金额为dp[i]。
• 如果偷，dp[i] = dp[i-2] + nums[i]; 不偷，则dp[i] = dp[i-1]; dp取最大值dp[i] = max(dp[i - 2] + nums[i], dp[i - 1])
• 注意判断dp公式之外的情况

213-打家劫舍-中等（房间结构是圆圈）

• 房间结构变成了一个圆圈，同样是不能同时偷相邻房间题目链接
• 把圆解开，因为首尾肯定有一个是不取的
• case1:去掉第一个房间，根据198题的算法，算最大值
• case2:去掉最后一个房间，算最大值
• 求最大值

337-打家劫舍III-中等（树形DP的入门题）

• 把房间的格局变成为二叉树结构题目链接

• 方法1：递归
  一个节点的金额数有两种情况，case 1:爷爷节点偷+四个孙子偷；case 2: 以及只有两个孩子偷； 所以需要后序遍历
  直接搜索超时，因此用记忆化搜索避免一些重复子问题（一个节点计算时会算其孩子和孙子节点的数值）

• 方法2： 动态规划，前面说到有重复计算，用到之前状态。在上面方法，其实对一个节点 偷与不偷得到的最大金钱都没有做记录，而是需要实时计算。而动态规划其实就是使用状态转移容器来记录状态的变化，避免实时计算，

  • 每个节点可选择偷或者不偷两种状态，根据题目意思，相连节点不能一起偷
  • 这里可以使用一个长度为2的数组，记录当前节点偷与不偷所得到的的最大金钱,0代表不偷，1代表偷
    当前节点选择偷时，那么两个孩子节点就不能选择偷了
    当前节点选择不偷时，两个孩子节点只需要拿最多的钱出来就行(两个孩子节点偷不偷没关系)

• 推荐参考链接：https://leetcode.cn/problems/house-robber-iii/solution/san-chong-fang-fa-jie-jue-shu-xing-dong-tai-gui-hu/

股票买卖问题

121-买卖股票的最佳时机-简单（最多一次买卖）

• 数组prices[i]代表股票当天的价格，设计一个算法，一次买卖赚到的最大钱数（赚不到钱返回0）题目链接
• 本质上就是求数组的一个最大差值，所以暴力解法两层循环，但其实一次循环就能找到最大差值（从前向后遍历，记录浏览过的最小值和已经遍历过的元素与其的最大差值）
• 动态规划解法

  • 两种状态：dp[i][0]第i天持有股票所得最多现金； dp[i][1]表示第i天不持有股票最多现金

  • 如果第i天持有股票即dp[i][0]， 那么可以由两个状态推出来
    第i-1天就持有股票，那么就保持现状，所得现金就是昨天持有股票的所得现金 即：dp[i - 1][0]
    第i天买入股票，所得现金就是买入今天的股票后所得现金即：-prices[i]（这里加粗是因为二刷的时候发现容易写成dp[i-1][1] - prices[i] ，但这种写法是下面122多次买卖的写法，如果最多一次买卖，转移方程直接用-prices[i] ）
    那么dp[i][0]应该选所得现金最大的，所以dp[i][0] = max(dp[i - 1][0], -prices[i]);

  • 如果第i天不持有股票即dp[i][1]， 也可以由两个状态推出来
    第i-1天就不持有股票，那么就保持现状，所得现金就是昨天不持有股票的所得现金 即：dp[i - 1][1]。
    第i天卖出股票，所得现金就是按照今天股票佳价格卖出后所得现金即：prices[i] + dp[i - 1][0]
    同样dp[i][1]取最大的，dp[i][1] = max(dp[i - 1][1], prices[i] + dp[i - 1][0]);

  • 初始化，dp[0][0] = -pricces[0]; dp[0][1] = 0;

• 因为只需要前面一个的状态，所以可以用滚动数组2*2优化空间，这里直接i%2即可

122-买卖股票的最佳时机II-中等（不限次数的买卖）

• 数组prices[i]代表股票当天的价格，设计一个算法，多次买卖赚到的最大钱数（不限制买卖次数）[题目链接](https://leetcode.cn/problems/best-time-to-buy-and-sell-stock-ii/）
• 与上题不同的是递推公式保持股票的状态要考虑前面的状态
  dp[i][0] = max(dp[i - 1][0], dp[i - 1][1] -prices[i]);

122-买卖股票的最佳时机III-困难（最多两次买卖）

• 数组prices[i]代表股票当天的价格，设计一个算法，最多两次买卖赚到的最大钱数[题目链接](https://leetcode.cn/problems/best-time-to-buy-and-sell-stock-iii/）
• 之前只有两种状态，保持和不保持股票
• 现在一天是有五种状态
  • 0 没有操作
  • 1 第一次保持
  • 2 第一次不保持
  • 3 第二次保持
  • 4 第二次不保持
• dp[i][j]中 i表示第i天，j为 [0 - 4] 五个状态，dp[i][j]表示第i天状态j所剩最大现金。
• dp[i][1] 包括当天买入和延续昨天保持状态； 所以dp[i][1] = max(dp[i - 1][1], dp[i - 1][0]-prices[i])
  其他状态同理

188-买卖股票的最佳时机4-困难（最多k次买卖）

• 上题进阶版，最多可进行k次买卖题目链接
• 和上题一样的套路，k次买卖，那一天有0-k*2种状态（找规律）
  • 奇数状态，保持股票， dp[i][k] = max(dp[i-1][k], dp[i - 1][k -1] - prices[i])
  • 偶数状态，不保持股票，dp[i][k] = max(dp[i - 1][k], dp[i - 1][k - 1] + prices[i])
• 一定要记得边界条件 prices.size() == 0

309-最佳买卖股票时机含冷冻期（买卖多次，冷冻期）

• 多次买卖一支股票，但卖出股票后，你无法在第二天买入股票 (即冷冻期为 1 天)。题目链接

• 老套路，找状态

• 一天的交易状态为: [持股, 不持股且过了冷冻期, 不持股且在冷冻期]
  dp[i][k]为第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][2]);
  • dp[i][2] = dp[i-1][0] + prices[i] 达到冷冻期的操作只有一个，前一天的卖出去

• 嘻嘻，自己写出来了

714-买卖股票的最佳时机含手续费-中等（买卖多次，手续费）

• 整数 fee 代表了交易股票的手续费用。你可以无限次地完成交易，但是你每笔交易都需要付手续费题目链接
• 本来感觉没什么难的，就是买入的时候减去一个数，但没真正理解注意里说的：交易是说买入卖出全过程，所以是在卖出的时候再减去fee, 而不是买入的时候
• 同时结果就要求最大值了，因为要收手续费，你不确定此时卖出是否赚钱
  return max(dp[prices.size() - 1][1], dp[prices.size() - 1][10);

子序列问题

300-最长递增子序列-中等 + 674-最长连续递增子序列-简单

• 如题，题目链接
• dp[i] 原本想的是在长度为i的数组中最长严格递增子序列长度为dp[i]，但实际是以num[i]结尾的最长递增子序列长度，所以最后结果要找一个最大值
• 对于nums[i],对于每一个比它小的num[j], j <i, nums[j]< nums[i]; dp[i] = dp[j] + 1;
• 注意点：返回dp[i]的最大值，
• 674-最长连续递增子序列-，比可以间断的简单，动规或者贪心，没啥可说的。题目链接

718-最长重复子数组-中等

• 两个数组找最长重复子数组，重点是子数组是连续的，不能间隔。题目链接
• 易错点：原本以为是lcp问题，后来发现是理解错误。下次做题需要思考题目出现的各种情况，读懂题目再去做
• 一般时在dp矩阵前加一行一列，方便计算.照顾边界情况，俗称为哨兵思想
• 注意点：在滚动数组实现时，注意每一轮，如果两个数组对应数不相等，记得赋值为0

if(nums1[i-1] == nums2[j-1])
       dp[j] = dp[j - 1] + 1;
  else
       dp[j] = 0; //注意要赋0操作，因为不相等的时候为0，重新计算
       
1
2
3
4
5
6

1143-最长公共子序列-中等 + 1035-不相交的线-中等

• lcp问题，题目链接
  - 关键点：递推公式

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] );
1
2
3
4

• 另一个注意点时在dp矩阵前加一行和一列，方便计算
• 1035题看着挺唬人，实际就是lcp问题换了张皮，一样的解法

53-最大子数组和-简单

• 取一个数组的子数组，让其和最大（数组有正负数）题目链接
• 暴力解法，贪心解法，动态规划解法，分治解法
• 此处动规解法：dp[i]为以nums[i]结尾的数组的最大值
• dp[i] = max(nums[i], dp[i-1] + nums[i])，因为nums[i]只有两种选择，加入前面的数组，或者自己新开一个数组，然后取最大值
• 还有个分治法，后面再补充

392-判断子序列-简单

• 判断s是否是t的子序列题目链接
• 简单解法，直接遍历
• 动态规划解法,其实就是相当于lcp的变式，只不过字符串s不允许删除
  • dp[i][j] 表示以下标i-1为结尾的字符串s，和以下标j-1为结尾的字符串t，相同子序列的长度为dp[i][j]
  • 如果s[i - 1] == t[i - 1], 那么dp[i][j] = dp[i-1][j-1]+1;
  • 否则，此时只是删除t的元素（略过t[i-1]), dp[i][j] = dp[i][j - 1]
• 进阶版是如何判断成万上亿条子序列s，日后思考
• https://leetcode.cn/problems/is-subsequence/solution/dui-hou-xu-tiao-zhan-de-yi-xie-si-kao-ru-he-kuai-s/

115-不同的子序列-困难

• 给定一个字符串 s 和一个字符串 t ，计算在 s 的子序列中 t 出现的个数。如s = bagg, t = bag, 题目链接
• 思想感觉挺难理解的，
• 1、dp[i][j]代表以i-1为结尾的s子序列中出现以j-1为结尾的t的个数为dp[i][j]。
• 2、抓住 “选”，s 要照着 t 来挑选，逐字符考察选或不选(是否删除该字符)，分别来到什么状态？
  举例，s 为babgbag，t 为bag，
  • 末尾字符相同，于是 s 有两种选择：
    case 1:用s[s.length-1]去匹配掉t[t.length-1]，问题规模缩小：继续考察babgba和ba
    case 2:不这么做，但t[t.length-1]仍需被匹配，于是在babgba中继续挑，考察babgba和bag
    另外代码随想录举得一个例子，s = bagg, t = bag, s[3] = t[2], 如果不选择s[3], 那么是s[0]s[1]s[2]与t匹配；如果选择s[3]，是s[0]s[1]s[3]与t匹配
  • 末尾字符不相等，则只有case2的选择
  • 所以递推公式：

dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j]; if(s[i] == s[j])(左上方和上方)
dp[i][j] = dp[i - 1][j]; otherwise
1
2

• 3、初始化，dp[0][j] = 0; 其中dp[0][0] = 1; dp[i][0] = 1(相当于从s[0,i-1]中找空字符串“”)
• 注意点： long 类型报错溢出!!所以用了uint64_t
  vector<vector<uint64_t>> dp(s.size() +1, vector<uint64_t>(t.size() + 1, 0));

583-两个字符串的删除操作-中等

• 问最小的操作步数可以使word1与word2相等，其中每一步只能进行删除操作题目链接
• dp[i][j] 代表长度i和长度j的两个单词相同的最小步骤数
• 递推公式
  • 当word1[i - 1] == word2[j - 1], 那么dp[i][j] = dp[i - 1][j - 1]
  • 否则，达到相等有三个路径：假设当前word1[i - 1] = a, word2[j - 1] = b;
    case 1: 把a和b都删除, 需要2步
    case 2: 在a删除，需要一步，操作次数为dp[i - 1][j] + 1
    case 3： 把b删除，
• 初始化按dp的意义来
• 多个数值求最小值

 dp[i][j] = min({dp[i - 1][j - 1] + 2, dp[i][j - 1] + 1, dp[i - 1][j] + 1});
 // dp[i][j] = min(min(dp[i - 1][j - 1] + 2, dp[i][j - 1] + 1), dp[i - 1][j] + 1);
1
2

72-编辑距离-困难

• 问word1变成word2的最小编辑距离(每一步可增删改)题目链接
• dp[i][j] 代表长度为i的word1变为长度j的word2的最小编辑距离
• 当word1[i - 1] == word2[j - 1], 那么dp[i][j] = dp[i - 1][j - 1]
• 否则，达到相等有两三个路径：假设当前word1[i - 1] = a, word2[j - 1] = b;
  case 1: 把a 替换成b， 需要1步,dp[i-1][j-1] + 1
  case 2: 把a删除，需要一步， dp[i - 1][j] + 1
  case 3： word1插入b, 此时word1的长度不变，所以i不变，插入的b抵消了wort2的b,所以状态回退至 dp[i][j - 1]，然后 + 1
  case 3的一个例子，word1 = a, word2 = ab;
• 想清楚每种情况需要哪个旧状态
• • 第一次独立完成困难题，yes。刷题顺序真的重要，按着代码随想录顺序做题，逐渐加深理解，解决该类问题的能力也会逐渐提升，直至写出困难题目。

647-回文子串-中等

• 问字符串s的回文子串的数目（子串，subsring, 连续）题目链接
• 暴力解法,双层循环
• 动态规划解法
  1、**布尔类型的dp[i][j]：表示区间范围[i,j] （注意是左闭右闭）的子串是否是回文子串，如果是dp[i][j]为true，否则为false。注意i <= j **
  2、整体上是两种，就是s[i]与s[j]相等，s[i]与s[j]不相等这两种。
  当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][i] = true；
  3、遍历顺序要注意：dp[i][j]用到了do[i+1][j - 1], 是左下角，所以要从下向上计算
  4、时间复杂度O(n^2), 空间O(n^2)
• 双指针,空间优化
  • 时间复杂度O(n^2), 空间O(1)
  • 核心思想：从中心点向两侧扩展，相同则符合条件（extend函数）。中心点分为两种，一种是长度为1， 第二种是长度为2， 其他都可以由这两种扩展而得

for(int i = 0; i < s.size() ; i++){
        count += extend(s, i, i);
          count += extend(s, i, i+1);
   }
1
2
3
4

516-最长回文子序列-中等

• 求字符串s的最长回文子序列的长度题目链接（子序列可以不连续）
• 动态规划解法，和上题差不多的套路，注意一下初始化的值，刚开始整个矩阵都初始化为1，但其实是不对的，在反对角线的前一个对角线上会发生错误
  • dp[i][j] 在区间[i,j]的回文子串的最长长度 i <= j
  • 当s[i]== s[j],dp[i][j] = dp[i + 1][j - 1] + 2
  • 否则， dp[i][j] = max{dp[i][j], dp[i + 1][j], dp[i][j-1]} //可以理解为全删除，或者删除s[i]/s[j]
  • 初始化，dp[i][i] = 1;其他为0，
  • 根据递推公式，应该从下到上，从左到右

三、总结

1、什么问题适合用动态规划？

• 一些回溯暴力搜索超时的问题
• 背包问题
• 一般问最大或最小数量(最值问题)，组合数的，可以考虑用动态规划
• 需要重复计算，用到之前状态的

2、如何完成动态规划过程？

• 按五个步骤逐步进行，一般问的是什么问题，dp[i]的意义即是这个

3、如何得到推导公式？

• 分析递推公式时需要聚焦到局部，思维不要发散
• 推导公式即有哪几种方式到达该状态，每一种方式可能用到哪些旧状态
• leetcode上没有纯01背包的问题，都是01背包应用方面的题目，也就是需要转化为01背包问题，转换的思路是最关键的，即确定题目中哪些代表weight ，哪些代表value， 再代入公式，就可以得到推导公式（01背包无非就是取或者不取两种情况）

4、注意

• 注意判断dp矩阵边界的情况