本文主要是介绍代码随想录 刷题记录-22 动态规划（6）习题，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
1.300.最长递增子序列
子序列问题是动态规划解决的经典问题，当前下标i的递增子序列长度，其实和i之前的下标j的子序列长度有关系.
动规五部曲：
1.dp数组及下标含义
dp[i] : 从任意位置开始，以nums[i]元素作为结尾的所有 递增子序列中，最长的子序列长度为 dp[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.初始化
每一个i，对应的dp[i]（即最长递增子序列）起始大小至少都是1.
4.遍历顺序
正序遍历
5.dp模拟
输入：[0,1,0,3,2]，dp数组的变化如下：
最后遍历dp数组，返回dp数组中最大的元素（覆盖所有的可能）
总结
本题最关键的是要想到dp[i]由哪些状态可以推出来，并取最大值，那么很自然就能想到递推公式：dp[i] = max(dp[i], dp[j] + 1);
代码如下：
class Solution {public int lengthOfLIS(int[] nums) {int[] dp = new int[nums.length];for(int i = 0 ; i < nums.length ; i++){dp[i] = 1;}for(int i = 0 ; i < nums.length ; i++){for(int j = 0 ; j < i ; j++){if(nums[j] < nums[i]) dp[i] = Math.max(dp[i],dp[j]+1);}}int result = 0 ;for(int i = 0 ; i < nums.length ; i++){result = Math.max(result,dp[i]);}return result;}
}2.674. 最长连续递增序列
贪心思想
局部最优：当前数比前一个数大，则局部解+1；否则重新开始
全局最优：最长的连续递增序列长度即最大的局部解
代码如下：
class Solution {public int findLengthOfLCIS(int[] nums) {//贪心int tmp = 1;int result = 0;for (int i = 1 ; i < nums.length ; i++){if(nums[i] > nums[i-1]) tmp++;else{result = Math.max(result,tmp);tmp = 1;}}result = Math.max(tmp,result);return result;}
}动态规划：
1.dp数组及下标含义
dp[i] : 以nums[i]结尾，nums[i]前任意一个元素开头，最长连续递增序列长度为 dp[i]
2.递推方程
if(nums[i] > nums[i-1]) dp[i] = dp[i-1] + 1;
3.初始化
dp[i] = 1;
4.遍历顺序
正序遍历
5.dp模拟
已输入nums = [1,3,5,4,7]为例，dp数组状态如下：
最后遍历dp，返回最大值。
代码如下：
class Solution {public int findLengthOfLCIS(int[] nums) {int[] dp = new int[nums.length];for(int i = 0; i < nums.length ; i++){dp[i] = 1;}for(int i = 1 ; i < nums.length ; i++){if(nums[i] > nums[i-1]) dp[i] = dp[i-1] + 1; }int result = 0;for(int i = 0 ; i < nums.length ; i++){result = Math.max(result,dp[i]);}return result;}
}3.718. 最长重复子数组
题目中说的子数组，是连续子序列。
（子数组的定义中要求元素连续）
如果是暴力的解法 只需要先两层for循环确定两个数组起始位置，然后再来一个循环可以是for或者while，来从两个起始位置开始比较，取得重复子数组的长度。
本题其实是动规解决的经典题目，我们只要想到 用二维数组可以记录两个字符串的所有比较情况，这样后面的可以利用前面的计算结果，比较好推递推公式。
动规五部曲分析如下：
1.dp数组及下标含义
dp[i][j] ：以下标i - 1为结尾的A，和以下标j - 1为结尾的B，最长重复子数组长度为dp[i][j]。
p[i][j]的定义也就决定着，我们在遍历dp[i][j]的时候i 和 j都要从1开始。
定义dp[i][j]为 以下标i为结尾的A，和以下标j 为结尾的B，最长重复子数组长度。不行么？
行倒是行！ 但实现起来就麻烦一点，需要单独处理初始化部分
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】是以i-1与j-1号元素作为结尾的公共子数组的长度. 即 公共子数组的结尾必须是i-1和j-1, 所以,当i-1 != j-1 时, dp【i】【j】=0, 如果相同 dp【i】【j】 = dp【i-1】【j-1】+1
3.初始化
根据dp[i][j]的定义，dp[i][0] 和dp[0][j]其实都是没有意义的！
但dp[i][0] 和dp[0][j]要初始值，因为 为了方便递归公式dp[i][j] = dp[i - 1][j - 1] + 1;
所以dp[i][0] 和dp[0][j]初始化为0。
举个例子A[0]如果和B[0]相同的话，dp[1][1] = dp[0][0] + 1，只有dp[0][0]初始为0，正好符合递推公式逐步累加起来。
4.确定遍历顺序
外层for循环遍历A，内层for循环遍历B，或者反过来。
题目要求长度最长的子数组的长度。所以在遍历的时候顺便把dp[i][j]的最大值记录下来。
5.dp模拟
拿示例1中，A: [1,2,3,2,1]，B: [3,2,1,4,7]为例，画一个dp数组的状态变化，如下：
代码如下：
class Solution {public int findLength(int[] nums1, int[] nums2) {int[][] dp = new int[nums1.length+1][nums2.length+1];int result = 0;for(int i = 1 ; i <= nums1.length ; i++){for(int j = 1 ; j <= nums2.length ;j++){if(nums1[i-1]==nums2[j-1]){dp[i][j] = dp[i-1][j-1] + 1;result = Math.max(result,dp[i][j]);}else dp[i][j] = 0;}}return result;}
}滚动数组优化：
class Solution {public int findLength(int[] nums1, int[] nums2) {int[] dp = new int[nums2.length+1];int result = 0;for(int i = 1; i <= nums1.length ; i++){for(int j = nums2.length ; j >= 1 ; j--){if(nums1[i-1] == nums2[j-1]){dp[j] = dp[j-1] + 1;result = Math.max(dp[j],result);}else dp[j] = 0; // 注意这里不相等的时候要有赋0的操作}}return result;}
}个人认为dp数组的定义不应该这么绕，这么绕容易出错：
定义dp[i][j]为 以下标i为结尾的A，和以下标j 为结尾的B，最长重复子数组长度，那么 第一行和第一列毕竟要进行初始化，如果nums1[i] 与 nums2[0] 相同的话，对应的 dp[i][0]就要初始为1， 因为此时最长重复子数组为1。 nums2[j] 与 nums1[0]相同的话，同理。
代码如下：
class Solution {public int findLength(int[] nums1, int[] nums2) {int[][] dp = new int[nums1.length][nums2.length];int result = 0;for(int i = 0; i < nums1.length ; i++){if(nums1[i] == nums2[0]) dp[i][0] = 1;}for(int j = 0; j < nums2.length ; j++){if(nums2[j] == nums1[0]) dp[0][j] = 1;}for(int i = 1 ; i < nums1.length ; i++){for(int j = 1 ; j < nums2.length ; j++){if(nums1[i] == nums2[j]){dp[i][j] = dp[i-1][j-1] + 1;}else{dp[i][j] = 0;}result = Math.max(result,dp[i][j]);}}for(int i = 0 ; i < nums1.length ; i++) result = Math.max(result,dp[i][0]);for(int j = 0 ; j < nums2.length ; j++) result = Math.max(result,dp[0][j]);return result;}
}这里在过程中保留最大的result还是在结束时遍历dp数组找到最大的result都可以，但是像上面这样的话还要检查一下初始化边界，防止遗漏。
4.1143.最长公共子序列
这里与上一题不同的就是不要求连续了
动规五部曲分析如下：
1.dp数组及下标含义
dp[i][j] : 考虑到 text1[i] 和 text2[j] ，能够求得的最长公共子序列长度为 dp[i][j]
2.递推公式
根据dp数组定义，向前寻找dp[i][j]的来源推导递推公式。
相比于dp[i-1][j-1]，多了text1[i],text2[j] ，if(text1[i] == text2[j]) ,dp[i][j] = dp[i-1][j-1] + 1;
else dp[i][j] = Math.max(dp[i-1][j],dp[i][j-1])
3.初始化
初始化第一行和第一列，如果有对应相等的值，那么赋1，其他初始化0
4.遍历顺序
根据递推公式的依赖关系，从上到下，从左到右遍历
5.dp模拟
由于本题递推中需要的是左边的值、上边的值和左上的值，如果要进行滚动数组优化，数组需要有2行。
代码如下：
class Solution {public int longestCommonSubsequence(String text1, String text2) {int[][] dp = new int[text1.length()][text2.length()];int i,j;for(i = 0 ; i < text1.length() ; i++){if(text1.charAt(i) == text2.charAt(0)){dp[i][0] = 1;break;}}while(i < text1.length()){dp[i++][0] = 1;}for(j = 0 ; j < text2.length() ; j++){if(text2.charAt(j) == text1.charAt(0)){dp[0][j] = 1;break;}}while(j < text2.length()){dp[0][j++] = 1;}for(i = 1 ; i < text1.length() ; i++){for(j = 1 ; j < text2.length() ;j++){if(text1.charAt(i) == text2.charAt(j)) dp[i][j] = dp[i-1][j-1] + 1;else dp[i][j] = Math.max(dp[i-1][j],dp[i][j-1]);}}return dp[text1.length()-1][text2.length()-1];}
}这里的初始化要考虑到子序列是不要求连续的，注意初始化的逻辑。
如果追求不初始化，则dp[i][j]定义为：考虑到text1[i-1]和text2[j-1],最长公共子序列长度是dp[i][j]：
class Solution {public int longestCommonSubsequence(String text1, String text2) {int m=text1.length(),n=text2.length();int[][] l=new int[m+1][n+1];for(int i=0;i<=m;i++){for(int j=0;j<=n;j++){if(i==0||j==0) l[i][j]=0;else if(text1.charAt(i-1)==text2.charAt(j-1)) l[i][j]=l[i-1][j-1]+1;else l[i][j]=Math.max(l[i-1][j],l[i][j-1]);}}return l[m][n];}
}对初始化的解释：
test1[0, i-1]和空串的最长公共子序列自然是0，所以dp[i][0] = 0;
同理dp[0][j]也是0。
5.1035.不相交的线
题目要求直线不能相交，这就是说明在字符串A中找到一个与字符串B相同的子序列，且这个子序列不能改变相对顺序，只要相对顺序不改变，链接相同数字的直线就不会相交。
本题说是求绘制的最大连线数，其实就是求两个字符串的最长公共子序列的长度。
代码如下：
class Solution {public int maxUncrossedLines(int[] nums1, int[] nums2) {int[][] dp = new int[nums1.length+1][nums2.length+1];for(int i = 0; i <= nums1.length ; i++){for(int j = 0 ; j <= nums2.length ; j++){if(i==0 || j==0) dp[i][j] = 0;else if(nums1[i-1] == nums2[j-1]) dp[i][j] = dp[i-1][j-1] + 1;else dp[i][j] = Math.max(dp[i-1][j],dp[i][j-1]);}}return dp[nums1.length][nums2.length];}
}6.53. 最大子序和
思路一 贪心
class Solution {public int maxSubArray(int[] nums) {int result = nums[0];int tmp = 0;for(int i = 0 ; i <nums.length ; i++){tmp += nums[i];result = Math.max(result,tmp);if(tmp < 0) tmp = 0;}return result;}
}思路二 动态规划
1.dp数组及下标含义
dp[i] : 以 nums[i] 为结尾的最大连续子序列和为 dp[i]
2.递推公式
dp[i] = Math.max(nums[i] , dp[i-1] + nums[i])
3.初始化
根据递推公式，dp[i]最初来源于dp[0]，根据定义
dp[0] = nums[0];
4.遍历顺序
正序遍历
5.dp模拟
以示例一为例，输入：nums = [-2,1,-3,4,-1,2,1,-5,4]，对应的dp状态如下：
最后遍历dp，返回最大值。代码如下：
class Solution {public int maxSubArray(int[] nums) {int[] dp = new int[nums.length];dp[0] = nums[0];int result = dp[0];for(int i = 1 ; i < nums.length ; i++){dp[i] = Math.max(dp[i-1]+nums[i],nums[i]);result = Math.max(result,dp[i]);}return result;}
}7.392.判断子序列
方法一 暴力回溯
时间超限
class Solution {String t;Set<String> set = new HashSet<>();List<Character> path = new ArrayList<>();public boolean isSubsequence(String s, String t) {//暴力回溯if(s.length() == 0) return true;this.t = t;dfs(0);return set.contains(s);}public void dfs(int startIndex){StringBuilder sb = new StringBuilder();for(Character c : path){sb.append(c);}set.add(sb.toString());if(startIndex == t.length()){return ;}for(int i = startIndex ; i < t.length() ; i++){path.add(t.charAt(i));dfs(i+1);path.remove(path.size()-1);}}
}方法二 双指针法
涉及到两个字符串比较，考虑双指针法
class Solution {public boolean isSubsequence(String s, String t) {if(s.isEmpty()) return true;int i = 0 , j = 0;for(j = 0 ; j < t.length() ; j++){if(s.charAt(i) == t.charAt(j)){i++;if(i==s.length()) break;}}return i == s.length();}
}双指针法的空间性能和时间性能都很好
方法三 动态规划
视为特殊的编辑距离问题
1.确定dp数组（dp table）以及下标的含义
dp【i】【j】理解为s【0:i】，t【0:j】两个字符串的以s【i-1】结尾的最长公共子序列的长度。
2.确定递推公式
在确定递推公式的时候，首先要考虑如下两种操作，整理如下：
- 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;，因为找到了一个相同的字符，相同子序列长度自然要在dp[i-1][j-1]的基础上加1（如果不理解，在回看一下dp[i][j]的定义）
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];
其实这里 大家可以发现和 1143.最长公共子序列 的递推公式基本那就是一样的，区别就是 本题 如果删元素一定是字符串t，而 1143.最长公共子序列 是两个字符串都可以删元素。
3.初始化
从递推公式可以看出dp[i][j]都是依赖于dp[i - 1][j - 1] 和 dp[i][j - 1]，所以dp[0][0]和dp[i][0]是一定要初始化的。
这里大家已经可以发现，在定义dp[i][j]含义的时候为什么要表示以下标i-1为结尾的字符串s，和以下标j-1为结尾的字符串t，相同子序列的长度为dp[i][j]。
因为这样的定义在dp二维矩阵中可以留出初始化的区间，如图：
如果要是定义的dp[i][j]是以下标i为结尾的字符串s和以下标j为结尾的字符串t，初始化就比较麻烦了。
dp[i][0] 表示以下标i-1为结尾的字符串，与空字符串的相同子序列长度，所以为0. dp[0][j]同理。
vector<vector<int>> dp(s.size() + 1, vector<int>(t.size() + 1, 0));4.确定遍历顺序
同理从递推公式可以看出dp[i][j]都是依赖于dp[i - 1][j - 1] 和 dp[i][j - 1]，那么遍历顺序也应该是从上到下，从左到右
5.dp模拟
以示例一为例，输入：s = "abc", t = "ahbgdc"，dp状态转移图如下：
dp[i][j]表示以下标i-1为结尾的字符串s和以下标j-1为结尾的字符串t 相同子序列的长度，所以如果dp[s.size()][t.size()] 与 字符串s的长度相同说明：s与t的最长相同子序列就是s，那么s 就是 t 的子序列。
这里dp[i][j] 表示 以 s.charAt(i-1)结尾 和 t.charAt(j-1)结尾的字符串的相同子序列长度 为dp[i][j]的目的就是为了方便初始化。
按这个定义第一行都初始化为0。
如果以 s.charAt(i)结尾 和 t.charAt(j)结尾的字符串的相同子序列长度 为dp[i][j]的话，那么第一行要拿出s的第一个字符逐个与t比较，相等则赋1，否则为0.
代码如下：
class Solution {public boolean isSubsequence(String s, String t) {int[][] dp = new int[s.length()+1][t.length()+1];for(int i = 1 ; i <= s.length() ; i++){for(int j = 1 ; j <= t.length() ; j++){if(s.charAt(i-1) == t.charAt(j-1)) dp[i][j] = dp[i-1][j-1] + 1;else dp[i][j] = dp[i][j-1];}}return dp[s.length()][t.length()] == s.length();}
}- 时间复杂度：O(n × m)
- 空间复杂度：O(n × m)
怀疑本题dp数组定义有问题，建议这么做：使用lcs代码 return lcs(s,t) == s.length();
8.115.不同的子序列
1.确定dp数组及下标含义
dp[i][j] : 在s[0:i] 中有 dp[i][j]个 t[0:j]的匹配
s[0:i] 是s中下标从0到i-1组成的字符串
t[0:j] 是t中下标从0到j-1组成的字符串
2.递推公式
如果s[i-1] == t[j-1] , dp[i][j]由两部分组成：
（1）继承原本就有的情况，不考虑s[i-1] , s[i-2]及之前中与 t[0:j]的匹配数 dp[i-1][j]
（2）新增情况，考虑s[i-1] == t[j-1] ，两边同时去掉最后一个字母还是原来的结果，新增匹配数量为dp[i-1][j-1]
dp[i][j] = dp[i-1][j] + dp[i-1][j-1]
如果 s[i-1] != t[j-1] ,那么就不考虑 s[i-1]
dp[i][j] = dp[i-1][j]
3.初始化
根据递推公式，dp[i][0] 和 dp[0][j]必须初始化
根据定义 dp[i][0] 表示空字符串在 s[0:i] 中的匹配数，为1（s一直删除，删除到空字符串为止，为1）
根据定义 dp[0][j] 表示 t[0:j]在 空字符串中的匹配数，为0
4.遍历顺序
根据递推公式，需要正序遍历，从上到下，从左到右。
5.dp模拟
以s："baegg"，t："bag"为例，推导dp数组状态如下：
代码如下：
class Solution {public int numDistinct(String s, String t) {int[][] dp = new int[s.length()+1][t.length()+1];for(int i = 0; i <= s.length() ; i++){dp[i][0] = 1;}for(int i = 1 ; i <= s.length() ; i++){for(int j = 1 ; j <= t.length() ; j++){if(s.charAt(i-1)==t.charAt(j-1)){dp[i][j] = dp[i-1][j] + dp[i-1][j-1];}else{dp[i][j] = dp[i-1][j];}}}return dp[s.length()][t.length()];}
}关于dp数组的定义：
"增长"或"连续" dp[i]都是以 nums[i-1]结尾, 其余都是 nums[0:i]
9.583. 两个字符串的删除操作
本题可以套用lcs的方法：
public int minDistance(String word1, String word2) {int[][] dp = new int[word1.length()+1][word2.length()+1];for(int i = 1 ; i <= word1.length() ; i++){for(int j = 1 ; j <= word2.length() ; j++){if(word1.charAt(i-1)==word2.charAt(j-1)){dp[i][j] = dp[i-1][j-1]+1;}else{dp[i][j] = Math.max(dp[i-1][j],dp[i][j-1]);}}}return word1.length()+word2.length()-2*dp[word1.length()][word2.length()];}动态规划方法：
1.dp数组及下标含义
dp[i][j] : s[0:i] 与 t[0:j] 达到相等所需要的最小删除次数。
2.递推公式
s[i-1] == t[j-1]时，由于最后一位相等，不需要删除，不会因此增加删除次数
dp[i][j] = dp[i-1][j-1]
s[i-1] != t[j-1]时候，考虑两种情况
（1）s[0:i-1] 与 t[0:j] 达到相等，所需要的最小删除次数 + 删除 s[i-1]的 1次次数
（2）s[0:i] 与 t[0:j-1]达到相等，所需要的最小删除次数 + 删除 t[j-1] 的 1次次数
dp[i][j] = Math.min(dp[i-1][j],dp[i][j-1) + 1;
3.初始化
根据递推公式，需要初始化dp[i][0] 与 dp[0][j]
根据定义 dp[i][0] = i ; dp[0][j] = j;
4.遍历顺序
从上到下，从左到右
5.dp模拟
以word1:"sea"，word2:"eat"为例，推导dp数组状态图如下：
代码如下：
class Solution {public int minDistance(String word1, String word2) {int[][] dp = new int[word1.length()+1][word2.length()+1];for(int i = 0 ; i <= word1.length() ; i++){dp[i][0] = i;}for(int j = 0 ; j <= word2.length() ; j++){dp[0][j] = j;}for(int i = 1 ; i <= word1.length() ; i++){for(int j = 1 ; j <= word2.length() ; j++){if(word1.charAt(i-1) == word2.charAt(j-1)){dp[i][j] = dp[i-1][j-1];}else{dp[i][j] = Math.min(dp[i-1][j],dp[i][j-1])+1;}}}return dp[word1.length()][word2.length()];}
}动态规划定义 dp[i][j] : word1[0:i] 与 word2[0:j]操作至相同所需要的最小操作次数是dp[i][j]
递推方程：
word1[i-1] == word2[j-1] 则 dp[i][j] = dp[i-1][j-1];
word1[i-1] != word2[j-1] 则 dp[i][j] = Math.min(dp[i-1][j-1] + 2, dp[i-1][j] + 1,dp[i][j-1]+1);
10.72. 编辑距离
编辑距离是用动规来解决的经典题目
1.确定dp数组及下标含义
dp[i][j] : 表示要把 word1[0:i] 转换成 word2[0:j]所需要的最小编辑次数
2.递推方程
在确定递推公式的时候，首先要考虑清楚编辑的几种操作，整理如下：
if (word1[i - 1] == word2[j - 1])不操作
if (word1[i - 1] != word2[j - 1])增删换考虑 word1[i-1] 与 word2[j-1]是否相等
if (word1[i - 1] != word2[j - 1])，此时就需要编辑了，如何编辑呢？
- 操作一：word1删除一个元素，那么就是以下标i - 2为结尾的word1 与 j-1为结尾的word2的最近编辑距离 再加上一个操作。
即 dp[i][j] = dp[i - 1][j] + 1;
- 操作二：word2删除一个元素，那么就是以下标i - 1为结尾的word1 与 j-2为结尾的word2的最近编辑距离 再加上一个操作。
即 dp[i][j] = dp[i][j - 1] + 1;
这里有同学发现了，怎么都是删除元素，添加元素去哪了。
word2添加一个元素，相当于word1删除一个元素，例如 word1 = "ad" ，word2 = "a"，word1删除元素'd' 和 word2添加一个元素'd'，变成word1="a", word2="ad"， 最终的操作数是一样！ dp数组如下图所示意的：
a a d+-----+-----+ +-----+-----+-----+| 0 | 1 | | 0 | 1 | 2 |+-----+-----+ ===> +-----+-----+-----+a | 1 | 0 | a | 1 | 0 | 1 |+-----+-----+ +-----+-----+-----+d | 2 | 1 |+-----+-----+3.初始化
根据递推方程，dp[i][0] ,dp[0][j]需要初始化
根据定义 dp[i][0] = i; dp[0][j] = j;
4.遍历顺序
从上到下，从左到右
5.dp模拟
以示例1为例，输入：word1 = "horse", word2 = "ros"为例，dp矩阵状态图如下：
代码如下：
class Solution {public int minDistance(String word1, String word2) {int[][] dp = new int[word1.length()+1][word2.length()+1];for(int i = 0 ; i <= word1.length() ; i++){dp[i][0] = i;}for(int j = 0; j <= word2.length() ; j++){dp[0][j] = j;}for(int i = 1 ; i <= word1.length() ; i++){for(int j = 1 ; j <= word2.length() ;j++){if(word1.charAt(i-1) == word2.charAt(j-1)) dp[i][j] = dp[i-1][j-1];else {//增加、删除//替换dp[i][j] = Math.min(dp[i-1][j] + 1,Math.min( dp[i][j-1] + 1, dp[i-1][j-1] + 1 ));}}}return dp[word1.length()][word2.length()];}
}编辑距离总结篇
参考：动态规划之编辑距离总结篇
11.647. 回文子串
思路
暴力解法
两层for循环，遍历区间起始位置和终止位置，然后还需要一层遍历判断这个区间是不是回文。所以时间复杂度：O(n^3)
动态规划
动规五部曲：
1.确定dp数组（dp table）以及下标的含义
如果大家做了很多这种子序列相关的题目，在定义dp数组的时候 很自然就会想题目求什么，我们就如何定义dp数组。
绝大多数题目确实是这样，不过本题如果我们定义，dp[i] 为 下标i结尾的字符串有 dp[i]个回文串的话，我们会发现很难找到递归关系。
dp[i] 和 dp[i-1] ，dp[i + 1] 看上去都没啥关系。
所以我们要看回文串的性质。 如图：
我们在判断字符串S是否是回文，那么如果我们知道 s[1]，s[2]，s[3] 这个子串是回文的，那么只需要比较 s[0]和s[4]这两个元素是否相同，如果相同的话，这个字符串s 就是回文串。
那么此时我们是不是能找到一种递归关系，也就是判断一个子字符串（字符串下标范围[i,j]）是否回文，依赖于，子字符串（下标范围[i + 1, j - 1]）） 是否是回文。
所以为了明确这种递归关系，我们的dp数组是要定义成一位二维dp数组。
布尔类型的dp[i][j]：表示区间范围[i,j] （注意是左闭右闭）的子串是否是回文子串，如果是dp[i][j]为true，否则为false。
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][j]全都初始化成false
4.遍历顺序
从递推公式中可以看出，情况三是根据dp[i + 1][j - 1]是否为true，在对dp[i][j]进行赋值true的。
dp[i + 1][j - 1] 在 dp[i][j]的左下角，如图：
如果这矩阵是从上到下，从左到右遍历，那么会用到没有计算过的dp[i + 1][j - 1]，也就是根据不确定是不是回文的区间[i+1,j-1]，来判断了[i,j]是不是回文，那结果一定是不对的。
所以一定要从下到上，从左到右遍历，这样保证dp[i + 1][j - 1]都是经过计算的。
有的代码实现是优先遍历列，然后遍历行，其实也是一个道理，都是为了保证dp[i + 1][j - 1]都是经过计算的。
5.dp模拟
举例，输入："aaa"，dp[i][j]状态如下：
图中有6个true，所以就是有6个回文子串。
注意因为dp[i][j]的定义，所以j一定是大于等于i的，那么在填充dp[i][j]的时候一定是只填充右上半部分。
代码如下：
class Solution {public int countSubstrings(String s) {int result =0;boolean[][] dp = new boolean[s.length()][s.length()];for(int i = s.length()-1 ; i >= 0 ; i--){for(int j = i ; j < s.length() ; j++){if(s.charAt(i) == s.charAt(j)){if(j - i <= 1){dp[i][j] = true;result ++;}else if(dp[i + 1][j - 1]){dp[i][j] = true;result ++;}}}}return result;}
}总结
本题的dp数组定义比较特殊，是根据回文串的性质来定义的，据此推得的递推方程和遍历顺序也与一般的动态规划题目不同。
12.516.最长回文子序列
回文子串是要连续的，回文子序列可不是连续的。
本题要比求回文子串简单一点，因为情况少了一点。
动规五部曲分析如下：
1.dp数组及下标含义
dp[i][j] : 字符串在下标 i 到 j 的范围内，最长回文子序列长度为dp[i][j]
2.递推公式
如果s[i]与s[j]相同，那么dp[i][j] = dp[i + 1][j - 1] + 2;
如图：
（如果这里看不懂，回忆一下dp[i][j]的定义）
如果s[i]与s[j]不相同，说明s[i]和s[j]的同时加入 并不能增加[i,j]区间回文子序列的长度，那么分别加入s[i]、s[j]看看哪一个可以组成最长的回文子序列。
加入s[j]的回文子序列长度为dp[i + 1][j]。
加入s[i]的回文子序列长度为dp[i][j - 1]。
那么dp[i][j]一定是取最大的，即：dp[i][j] = max(dp[i + 1][j], dp[i][j - 1]);
代码如下：
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]);
}3.初始化
首先要考虑当i 和j 相同的情况，从递推公式：dp[i][j] = dp[i + 1][j - 1] + 2; 可以看出 递推公式是计算不到 i 和j相同时候的情况。
所以需要手动初始化一下，当i与j相同，那么dp[i][j]一定是等于1的，即：一个字符的回文子序列长度就是1。
其他情况dp[i][j]初始为0就行，这样递推公式：dp[i][j] = max(dp[i + 1][j], dp[i][j - 1]); 中dp[i][j]才不会被初始值覆盖。
vector<vector<int>> dp(s.size(), vector<int>(s.size(), 0));
for (int i = 0; i < s.size(); i++) dp[i][i] = 1;4.遍历顺序
从递归公式中，可以看出，dp[i][j] 依赖于 dp[i + 1][j - 1] ，dp[i + 1][j] 和 dp[i][j - 1]，如图：
所以遍历i的时候一定要从下到上遍历，这样才能保证下一行的数据是经过计算的。
j的话，可以正常从左向右遍历。
5.dp模拟
输入s:"cbbd" 为例，dp数组状态如图：
红色框即：dp[0][s.size() - 1]; 为最终结果。
代码如下：
class Solution {public int longestPalindromeSubseq(String s) {int[][] dp = new int[s.length()+1][s.length()+1];for(int i = 0 ; i < s.length() ; i++) dp[i][i] = 1;for(int i = s.length()-1 ; i >= 0 ; i--){for(int j = i + 1 ; j < s.length() ; j++){if(s.charAt(i) == s.charAt(j)){dp[i][j] = dp[i+1][j-1] + 2;}else{dp[i][j] = Math.max(dp[i][j-1],dp[i+1][j]);}}}return dp[0][s.length()-1];}
}动态规划总结
参考：动态规划最强总结篇
这篇关于代码随想录 刷题记录-22 动态规划（6）习题的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
