leetcode动态规划:子序列问题汇总

300.最长递增子序列（不连续） - 解析 **
题目：给定一个数组，求最长子序列（不要求连续）长度
思路：求这种子序列、最长之类的问题，动态规划可能是一种解法（当然不一定能解）
思考：
1.dp数组定义
这道题的dp数组怎么定义。首先给定的是一个一维数组，那么先定义一个dp[i]，那么含义是什么呢，就是下标为i的情况下最长子序列长度为dp[i];
2.递推公式
在推导公式的时候，要想一下dp[i]的定义，那么公式就是0 - i-1的每个dp中的最长的，再 1（这个时候才求出了dp[i], 那么dp[i]就是最长吗？不一定，所有要再max比较一下），所以递推公式为：if (nums[i] > nums[j]) dp[i] = max(dp[i], dp[j] 1);
那么这个max是什么意思呢，为什么要来这么一下呢？还是上面那个解释，对于下标i，我们要比较0 - i-1中最长的子序列，再 1
3.初始化
还是看dp的含义，标识每个位置的最长长度，所以都初始化为1
4.代码简述：先定义一个一位dp，都初始化为1；两次循环，内层的注意下遍历范围是0 - i-1，然后符合递增条件的，需要比较0 - i-1中的每个dp值 1，得到最大dp值；再起一个变量保存最大结果

674.最长连续递增子序列（连续）
题目：和上一题一样，就是要求了要连续
思路：
要求连续的话，会简单一点，因为不需要再内层的for循环来比较每个0 - i-1来得到最大值了，直接比较后来判断就行

718.最长重复子数组（连续）
题目：两个数组，要最长的、公共的、重复的子数组（相当于上一道题的连续子序列）的长度
思路：两个数组了，应该就要定义二维dp数组了
1.dp数组
dp[i][j]，代表以下标i-1结尾的数组1，和j-1结尾的数组2，最长的连续子数组
这里的-1是为了初始化方便以及写代码好写（从这道题开始，后面会有不少定义-1的），要注意定义了-1后，比较的时候也要用-1来比较
2.递推公式
不要求递增，只要连续且相等就行；
由于这道题只能从dp[i-1][j-1]递推出来，dp[i][j] = dp[i-1][j-1] 1; 同时需要一个变量来存最大值

1142.最长公共子序列（不连续）
题目：要返回两个字符串的公共子序列最长长度
思路：和上一道题很像，不要求递增，不要求连续；
1.dp数组
表示长度为[0,i-1]的字符串text1和长度为[0,j-1]的字符串text2，最长公共子序列长度为dp[i][j]
2.递推公式
因为不要求连续，所以判断两个字符串的-1下标要分为相等和不相等；
若相等，则dp[i-1][j-1] 1; 若不相等（不相等为什么还要考虑呢），那就看看text1[0, i - 2]与text2[0, j - 1]的最长公共子序列 和 text1[0, i - 1]与text2[0, j - 2]的最长公共子序列，取最大的，即dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
最后的dp就是结果
疑问：为什么这个就要考虑不相等，为什么上一个就要新开一个变量来存最后的结果；
因为上一道题要求了连续，连续的话dp[i][j]只能由dp[i-1][j-1]来推导出来；而本题不要求连续，可以由dp[i-1][j-1] dp[i-1][j] dp[i][j-1] 都是可以推导的

53.最大子数组和（连续）
题目：一个数组，求最大的连续子数组，返回和
思考：
1.dp数组：
dp[i]：包括下标i（以nums[i]为结尾）的最大连续子序列和为dp[i]。
2.递推公式
遍历一遍数组，对于每个值，有两种情况，要不就是将这个值加到之前的dp[i-1]上，要不就是从这个值开始，重新开始；至于选择哪种，直接比较取两者中大的那个就可以；
当然得到此时的dp[i]后，需要顺便看一下是不是最大值，就是用一个变量存一下；
3.初始化
这会就不能初始化为0了，而是nums[0]
这道题为什么要一个变量存一下呢，因为dp[i]只是表示这个位置为结尾的最大值，而不是整体的
疑问：有没有可能，连续的需要变量，不连续的不需要，不连续的需要考虑不等的情况

从这里开始是编辑距离问题

392.判断子序列
题目：两个字符串，一个s是否为另一个t的子序列（不连续）
思考：根据上面的规律，不连续的可能不用变量存最大值，且每个值都需要处理
1.确定dp数组
dp[i][j]:以下标i-1为结尾的字符串s，和以下标j-1为结尾的字符串t，相同子序列的长度为dp[i][j]，注意定义的时候先定义成长度
2.递推公式
不连续的话：
if (s[i - 1] == t[j - 1])，那么dp[i][j] = dp[i - 1][j - 1] 1;
if (s[i - 1] != t[j - 1])，那么由于s <=t，dp[i][j] = dp[i][j - 1]

115.不同的子序列
题目：两个字符串s和t，求s的子序列（不连续）中t的个数
思考：不连续，用下上面的方法，可以理解为s中有多少个t
1.dp数组
dp[i][j]：以i-1为结尾的s子序列中出现以j-1为结尾的t的个数为dp[i][j]
2.递推公式
和上面的一样，考虑到不连续，需要两个数组中的每两个-1来进行比较
若相等，dp[i][j]又需要分为两个部分：
第一部分，s[i - 1] 与 t[j - 1]这两个值相等了，将相当于假设没有这两个值的话的dp值，就是dp[i-1][j-1]（也就是用s[i-1]）;
第二部分，就是不用s[i-1]，不用的话就是dp[i-1][j]（即s[i-2]结尾，t[i-1]结尾）
最后二者相加，就是最后的递推公式
若不相等，就是上面的不用s[i-1],即公式dp[i-1][j]
3.初始化
根据上面的递推公式，dp[i][j]可以由dp[i-1][j-1] 和 dp[i-1][j]方向推到过来，也就是上方和左上方，那么第一行就需要初始化，这一行是某个字符串出现空字符串的个数，所以初始化为1

583.两个字符串的删除操作
题目：两个字符串，都可以删除，最后求两个字符串相等的最小步数
思考：上一道题，其实没用的那个场景，相当于删除，但是只删除一个字符串的；本题是可删除两个字符串的；这个就不是子序列是，相当于连续的子串？
1.dp数组
dp[i][j]表示，以i-1结尾的字符串word1和以j-1结尾的字符串word2，要想达到相等，需要删除元素的最少次数
2.递推公式
当word1[i - 1] 与 word2[j - 1]相同的时候，dp[i][j] = dp[i - 1][j - 1];为啥等于-1呢，就相当于，两个字符串这个位置的值是相同的，那么删了也是一样的；
当word1[i - 1] 与 word2[j - 1]不相同的时候，就会有如下三种场景：
删掉word[i-1]，则有dp[i-1][j] 1
删掉word[j-1], 则有dp[i][j-1] 1
都删掉，则有dp[i - 1][j - 1] 2
后面这个1代表1步，2代表2步
3.初始化
这道题是要初始化的，根据dp的定义，表示word2是一个空字符串，那么以i-1结尾的word1，需要删除0-i-1共i个元素（i步），才能成为空串
再次思考：本题是不相等的时候又分了情况，上一题是相同的时候分了情况，为啥

72.编辑距离
题目：两个字符串，可以增删改，变成另一个，求最小步数
思考：
1.dp数组
表示以下标i-1为结尾的字符串word1，和以下标j-1为结尾的字符串word2，最近编辑距离为dp[i][j]
2.递推公式
相等的情况，同上一道题=dp[i-1][j-1]
不等的情况，就是分别删（两个字符串）和替换，三者取最小值
3.初始化的逻辑同上

0621再次回顾：

子序列问题这部分，目前写了12道题，分为如下三个模块：

• 普通子序列问题
• 编辑距离问题
• 回文问题

普通子序列问题分为：

• 最长递增子序列
• 最长连续递增子序列
• 最长重复子数组
• 最长重复子序列
• 最大子数组和

编辑距离问题分为：

• 判断子序列
• 不同的子序列
• 两个字符串的删除操作
• 编辑距离

回文问题分为：

• 回文子串
• 最长回文子串
• 最长回文子序列

上面这些问题主要区分就是是否连续：

• 如果题目已经说了，求连续的什么什么，那肯定时连续
• 如果是数组，求子数组，那是连续
• 如果是字符串，求子串，大概率是连续，得看看题目中有没有说明
• 一般说子序列，无特殊说明的话，是不连续

连续与否的区别是什么：（多数情况下）

• 连续：需要比较当前时刻的值和上一时刻的值，如满足，则怎么怎么样；一般没有else；那这样算出来的dp，不一定是那个时刻最大的，需要一个临时变量来比较下，暂存；
• 不连续：需要每次比较的时候来判断，相等条件怎么怎么样，不等条件下怎么怎么样，每次都对dp做了最大值的处理，这样最后的dp理论上就是最大值；

这篇好文章是转载于：学新通技术网