前言
上一章讲到“买卖股票的最佳时机”系列问题，进行了总结和归纳，本章咱们来看看该如何使用动态规划去解决有关“子序列”这一系列问题！
一、最长递增子序列
题目描述：
题目来源：300. 最长递增子序列
1.1、dp定义
分析：
首先来看一下我们要定义的dp[i]表示的就是题目中所描述的最长子序列长度，进一步，那么这段最长子序列长度是哪一段的长度呢？是以nums[i]为结尾的长度！
dp定义：
dp[i]：以nums[i]为结尾的最长递增子序列的长度。
大多数人的疑惑：
可能很多同学，看到这道题没有思路，就会去看题解，但是看了题解，也没弄清楚dp数组的含义~
一定要注意dp定义中，以nums[i]为结尾的子序列，就是说这段序列中必须包含数字nums[i]，并且，他一定是这段子序列的结尾！
1.2、递推公式
分析：
我们思考的方式因该是：从那些状态才能得出dp[i]？
具体的，如下图：
状态转移方程：
if（nums[j] < nums[i]）
dp[i] = Math.max(dp[i], dp[j] + 1)；
1.3、初始化
这里也需要考验你对dp定义的理解了~
dp[i]表示以nums[i]为结尾的最长递增子序列，既然是以xxx为结尾，那么说明长度至少为1！
因此，我们只需要给dp数组都初始化成1即可
1.4、注意
与以往我们做动态规划类的题目不同；
以前我们求出的dp[nums.length - 1]可能就是问题的解了；
但是此题不同的是，dp[nums.length - 1]代表的是以nums[nums.length - 1]为结尾的最长递增子序列，说明这个序列中一定包含nums[nums.length - 1]这个数字，那么，以这个数字为结尾的一定就是最长的递增子序列吗？
当然不是！
例如数组：{1,3,6,7,9,4,10,5,6}，他的最长递增子序列是以6为结尾吗？当然不是，以6为结尾的递增子序列有{1,3,4,5,6}，而已10为结尾的递增子序列有{1,3,6,7,9,10};
dp数组如下：
正好符合咱们的分析，因此我们需要结尾再加个循环遍历dp数组找出最大值，也可以在递推dp时加上一个 result = Math.max(dp[i], result) 找出dp数组中的最大值。
1.5、解题代码
class Solution {
public int lengthOfLIS(int[] nums) {
int[] dp = new int[nums.length];
//初始化
Arrays.fill(dp, 1);//以某一值为结尾，那么长度至少是1
int result = 1;//保存结果
//递推
for(int i = 1; i < nums.length; i++) {
for(int j = 0; j < i; j++) {
if(nums[j] < nums[i]) {//注意前是递增的序列才被比较添加
dp[i] = Math.max(dp[j] + 1, dp[i]);
}
}
result = Math.max(dp[i], result);
}
return dp[nums.length - 1];
}
}二、最长连续递增序列
题目描述：
题目来源 ：674. 最长连续递增序列
2.1、分析
本题与 “最长递增子序列” 唯一不同的就是连续，既然要求连续，就只需要对比nums[i]和nums[i - 1]即可，若nums[i] > nums[i - 1]，则“以nums[i]为结尾的最长连续递增序列”就可以由以nums[i - 1]为结尾的最长连续递增序列 + 1”得到；
Ps：本题结合着“最长递增子序列”分析，会更加容易理解；
2.2、解题代码
class Solution {
public int findLengthOfLCIS(int[] nums) {
int[] dp = new int[nums.length];
Arrays.fill(dp, 1);
int result = 1;
for(int i = 1; i < nums.length; i++) {
if(nums[i - 1] < nums[i]) {
dp[i] = dp[i - 1] + 1;
}
if(dp[i] > result) {
result = dp[i];
}
}
return result;
}
}三、最长重复子数组
题目描述：
题目来源：718. 最长重复子数组
3.1、dp定义
分析：
想要对比着两个数组去表示状态，那么我们可以用一个二维的数组去表示~
dp[i][j]为了对应最终的解，就表示最长重复子数组的长度了，那么可以如下这样定义；
dp定义：
dp[i][j]：以nums1的第i - 1个数字为结尾，以nums2的第i - 1个数字为结尾，最长重复子数组的长度。
为什么定义成以第i - 1个数字为结尾，而不是以第i个数字为结尾？
这样做是为了减少计算量，怎么就能减少计算量了？
如果我们这样去定义，那么dp[i][0]和dp[0][j]就是没有意义的，因为dp[i][0]表示“以nums1的第i - 1个数字为结尾，以nums2的第 -1 个数字为结尾”，数组下标是不可能为负数的，因此就是没有意义的，再对他初始化的时候，就可以直接初始化成零，因为对比着两个数组，只有两数组数字相同的时候才进行 + 1的操作（+1这里如果不理解，说明“最长递增子序列这道题”你还是没把握住，建议再回去看看那道题）
但是如果我们定义成以i为结尾，初始化的时候nums[i][0]和nums[0][j]该怎么初始化？dp[i][0]就是“nums1以nums1[i]为结尾，nums2以nums2[0]为结尾的最长子数组”，那么我们就需要揪住nums2[0]这个元素去遍历nums1这个数组，去统计相同的元素，同理，nums[0][j]也是如此！
建议：像这类的问题都建议定义成“以i - 1为结尾”，减少不必要的计算！
3.2、递推公式
分析：
dp[i][j]可以由哪些状态得来呢？
当 nums1[i - 1] == nums[j - 1] 时（为什么是 i - 1 前面已经讲过了），是可以由 dp[i - 1][j - 1] + 1 得到dp[i][j]，这时候你可能要问，“为什么不是 dp[i - 1][j] + 1 或者 dp[i][j - 1] + 1 得来的呢？”
原因如下图：
更深入的理解如下：
因为每一次比较都是一对字符进行比较，那么 +1 操作就表示这一对字符相同，所以才 +1 ，而要得到dp[i][j]这个状态，就需要i和j都向前跨越一个字符，站在这个视角，再比较i,j这对字符，若这对字符相同，就+1得到dp[i][j]。
递推公式：
if(nums1[i - 1] == nums2[j - 1])
dp[i][j] = dp[i - 1][j - 1] + 1；
3.3、初始化
全都是化成即可，dp[i][0]和dp[j][0]为什么初始化成0，dp定义中讲过了，其余的为什么初始化成0，是因为在递推公式的递推下，初始化的内容都会被覆盖，也就是说，其余的初始化成多少都可以；
3.4、解题代码
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;
}
if(result < dp[i][j]) {
result = dp[i][j];
}
}
}
return result;
}
}四、最长公共子序列
题目描述：
题目来源：1143. 最长公共子序列
4.1、分析
这道题和 “最长重复子数组” 很相似，不同的是子数组是连续的，而子序列可以是不连续的；
那么他们除了转移方程是不一样的，其他的处理都是一样的；
转移方程分析：
当 text1[i] == text2[j] 时，我们可以由上一个状态dp[i - 1][j - 1] + 1推出来，也就是由“以text1第 i - 2 个字符和以text2第就 j - 2 个字符的最长公共子序列加一”即可得到dp[i][j]；
为什么是i - 1, j - 1呢？
因为每一次比较都是一对字符进行比较，那么 +1 操作就表示这一对字符相同，所以才 +1 ，而要得到dp[i][j]这个状态，就需要i和j都向前跨越一个字符，站在这个视角，再比较i,j这对字符，若这对字符相同，就+1得到dp[i][j]。
当 text1[i] != text2[j] 时呢？dp[i][j]就等于 max(dp[i - 1][j], dp[i][j - 1])，原因如下图：
转移方程：
if(text1.charAt(i - 1) == text2.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]);
4.2、初始化及遍历顺序
初始化与“最长重复子数组”一样，忘记了可以在往回翻翻看~
由递推公式所需要的状态可以得出下图：
由上图可知，dp[i, j]可以由这几个位置得出，那么遍历顺序一定是从上到下，从左到右遍历的；
4.3、解题代码
class Solution {
public int longestCommonSubsequence(String text1, String text2) {
int len1 = text1.length();
int len2 = text2.length();
int[][] dp = new int[len1 + 1][len2 + 1];
int result = 0;
for(int i = 1; i <= len1; i++) {
for(int j = 1; j <= len2; j++) {
if(text1.charAt(i - 1) == text2.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]);
}
if(dp[i][j] > result) {
result = dp[i][j];
}
}
}
return result;
}
}五、不相交的线
题目描述：
题目来源：1035. 不相交的线
5.1、分析
如果你刚刷完上一题“最长公共子序列”，再去深入思考一下这道题，“线不能相交”也就表明序列是有序的，实际上就是在求公共子序列，几乎是一模一样，只是套了一个壳子~
如果有不理解的地方，建议再多去理解一下上面的求“最长公共子序列”问题！
5.2、解题代码
class Solution {
public int maxUncrossedLines(int[] nums1, int[] nums2) {
int len1 = nums1.length;
int len2 = nums2.length;
int[][] dp = new int[len1 + 1][len2 + 1];
int result = 0;
for(int i = 1; i <= len1; i++) {
for(int j = 1; j <= len2; j++) {
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]);
}
if(dp[i][j] > result) {
result = dp[i][j];
}
}
}
return result;
}
}六、最大子数组和
题目描述：
题目来源：53. 最大子数组和
6.1、dp定义
dp[i]表示以nums[i]为结尾的，最长连续子数组的和；（不理解的可以看看前面讲到的题，分析过很多遍了）
6.2、递推公式
分析：
如何才能得到dp[i]呢？其实就是两种状态，一种是延续之前的状态（之前累加过的数字），加上当前数字，也就是dp[i - 1] + nums[i]；还有一种就是重新进行累加，以当前数字的位置为起始位置，也就是nums[i]，我们只需要得出最大的数字即可，也就是看是否需要延续之前累加好的和，再加上当前数字；
递推公式：
dp[i] = Math.max(dp[i - 1] + nums[i], nums[i]);
6.3、初始化
分析：
从递推公式中可以看出，要得到dp[i]，需要知道dp[i - 1]，那么一直推到根源就是需要知道dp[0]，其他的值都可以根据dp[0]可以推导出来；
dp[0]表示以nums[0]为结尾的，最大子数组和，也就是nums[0]；
初始化：
dp[0] = nums[0]；
6.4、遍历顺序
有递推公式可以知道，要得到dp[i]，需要知道dp[i - 1]，也就是一个顺序遍历即可；另外，dp[nums.length - 1]并不是真正的结果，具体请看“最长递增子序列”这道题中的1.4注意；
6.5、解题代码
class Solution {
//最大子数组和(动态规划)
public int maxSubArray(int[] nums) {
int len = nums.length;
int[] dp = new int[len];
dp[0] = nums[0];
int result = nums[0];
for(int i = 1; i < len; i++) {
dp[i] = Math.max(dp[i - 1] + nums[i], nums[i]);
if(result < dp[i]) {
result = dp[i];
}
}
return result;
}
}
