注：按照代码随想录的刷题指南进行，自己总结补充，以加深印象
参考链接：https://leetcode-cn.com/circle/article/wGp7Y9/
题目来源：力扣（LeetCode）
一、基础知识
1、动态规划思想
动态规划中每一个状态一定是由前面的状态推导出来的
dp数组存储的是可维持的状态，而递推公式是达到该状态的动作
2、解题步骤（有用！）
- 确定dp数组（dp table）以及下标的含义
- 确定递推公式
- dp数组如何初始化
- 确定遍历顺序
- 举例推导dp数组
3、背包问题
3.1 01背包
问题 ：有n件物品和一个最多能背重量为w 的背包。第i件物品的重量是weight[i]，得到的价值是value[i] 。每件物品只能用一次，求解将哪些物品装入背包里物品价值总和最大。
- 每个物品都有取或者不取两种选择，则可以用回溯法暴力搜索，但时间是指数级别的复杂度,容易超时。
二维数组写法 ：
- dp[i][j] 表示从下标为[0-i]的物品里任意取，放进容量为j的背包，价值总和最大是多少
- 递推公式：两个方向，取与不取：
不取物品：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]}
- 初始化
如果背包容量j为0的话，即dp[i][0]，无论是选取哪些物品，背包价值总和一定为0。
dp[0][j]，即：i为0，存放编号0的物品的时候，各个容量的背包所能存放的最大价值。(j >= weight[0], dp[0][j] = value[0] ; 否则为0）
一般可以把数组全部初始化为0， 方便
- 遍历顺序
物品和背包容量的遍历顺序不限。（可以从递归公式的方向来看） - 举例
滚动数组写法（一维）
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]);
}
}
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;
}
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);
}
}
}
- 多重背包在面试中基本不会出现，力扣上也没有对应的题目，大家对多重背包的掌握程度知道它是一种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-不同的二叉搜索树-中等
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背包问题？
假设加法总和为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];
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][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，重新计算
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] );
- 另一个注意点时在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的选择
- 所以递推公式：
- 末尾字符相同，于是 s 有两种选择：
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
- 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);
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);
}
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矩阵边界的情况