数据结构与算法｜算法总结｜动态规划篇之子序列、子数组问题

首先我们要明确以下两个问题：
子序列：子序列是由数组派生而来的序列，删除（或不删除）数组中的元素而不改变其余元素的顺序。例如，[3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的子序列。
子数组：子数组是数组中的一个连续部分

好了现在开始做总结！

首先我们一起复习动规五部曲：

1. 确定 dp 数组以及下标含义
2. 确定递推公式
3. dp 数组如何初始化
4. 确定遍历顺序
5. 距离推导 dp 数组

然后建议搭配 数据结构与算法｜算法总结｜动态规划之编辑距离总结篇(或者叫两个序列之间的比较问题)食用。

⭐️300.最长递增子序列

力扣题目链接

文章讲解：300.最长递增子序列

视频链接：动态规划之子序列问题，元素不连续！| LeetCode：300.最长递增子序列
状态：子序列问题的开篇，主要是子序列问题思路的开端，非常重要。特别是关于他的dp数组，反复推敲反复琢磨：dp[i]表示i之前包括i的以nums[i]结尾的最长递增子序列的长度

这里需要提到的一个重点是：
对于递推公式：
$$dp[i]=max(dp[i],dp[j]+1)$$
这里的主要含义不是取其中的最大值，而是去遍历 dp[j]，拿到他的最大值。

既然这里有个 j 出现了，我们当然可以判断到：

if (nums[j] < nums[i]) dp[i] = max(dp[i], dp[j] + 1)

所以遍历顺序也很容易得到：

for (int i = 0; i < nums.size(); i++) {for (int j = 0; j < nums.size(); j++) {...}
}

674.最长连续递增序列

力扣题目链接

文章讲解：674.最长连续递增序列

视频讲解：动态规划之子序列问题，重点在于连续！| LeetCode：674.最长连续递增序列

状态：连续递增子序列和递增子序列区别在哪里？体现在代码中的话又在哪里呢？

• 首先之前的300.最长递增子序列只要求递增子序列，并不要求序列在数组是是一组连续的数，而本题要求连续的递增子序列。其实只要一连续，很明显就可以用贪心算法了(贪心算法的求解会放在最后面)；
• 再一个，代码中我们要求的连续的子序列，所以两次遍历肯定是不用了，只要每次发现连续小的话，直接来个+1即可。

这里我们可以使用贪心算法，某种程度来说，也可以使用滑动窗口来解决该问题，也就是说，只要一连续，尝试滑动窗口也是非常不错的选择。

但是在这里只描述动态规划的方法：

• 明确dp数组的含义
  跟上一题一样，以下标i为结尾的最长连续递增子序列的长度为dp[i]

• 确定递推公式
  在300.最长递增子序列中，我们的dp[i]是由i面前的某个元素j来进行推导。
  本题中我们求的是连续的递增子序列，所以我们没有必要去比较前面的所有元素了，在上一题中，我们可是遍历了0~i-1的j。
  所以如果我们nums[i] > nums[i-1]，我们就做对应的那个dp[i] + 1的操作，即：
  $dp[i]=dp[i-1]+1$

• dp数组的初始化
  以下标i为结尾的连续递增的子序列长度最少也应该是1，即就是nums[i]这一个元素。
  所以dp[i]应该初始1;

• 确定遍历顺序
  从递推公式上可以看出， dp[i + 1]依赖dp[i]，所以一定是从前向后遍历。

⭐️718.最长重复子数组

力扣题目链接

文章讲解：718.最长重复子数组

视频讲解：动态规划之子序列问题，想清楚DP数组的定义 | LeetCode：718.最长重复子数组
状态：题目风格开始突变！现在我们要比较的是两个数组！

其实如果我们能够提前知道这题使用动态规划，我们就可以拿 dp 数组去硬套！

题目要求返回 两个数组中 公共的 、长度最长的子数组的长度 。

我们可以设 dp 的含义为：dp[i][j] 表示分别以第 i - 1 和第 j - 1 结尾的数组 A 和数组 B公共的、长度最长的子数组。为什么这么设置呢？因为我们需要统一递推公式。等我们推理出递推公式之后自然可以理解。

那么递推公式应该是什么样的呢？其实我们对着两个数组稍微比较一下就知道了，如果想推理出第 i -1 个位置和第 i - 2 个位置的值，我们需要在前一个位置上 + 1，所以有：
$dp[i][j]=dp[i-1]dp[j-1]+1$

如果我们在设计 dp 数组含义的时候使用 dp[i][j] 表示分别以第 i 和第 j 结尾，那么我们如何计算 dp[0][0]呢？

至此，题目基本解决。

1143.最长公共子序列

力扣题目链接

文章讲解：1143.最长公共子序列

视频讲解：动态规划子序列问题经典题目 | LeetCode：1143.最长公共子序列
状态：本题其实就跟718.最长重复子数组类似，但是不要求连续了。

本题的难点我认为主要还是在：

1. 递推数组的分情况讨论：
   我们如何得出需要讨论这两个情况呢？因为我们对本题的 dp 数组的设计为：长度为[0, i - 1]的字符串text1与长度为[0, j - 1]的字符串text2的最长公共子序列为dp[i][j]。
   如果 i - 1 位置 和 j - 1 位置相等了，我们肯定就是把 i - 2 位置和 j - 2 位置的值 + 1；
   如果不想等，那么说明我们不能考虑同时考虑这两个位置的字母，选择比较 i - 2 与 j - 1 位置 or i - 1 位置 与 j - 2 位置

   • $if(test[i-1]==text2[j-1])$

   • $if(test[i-1]!=text2[j-1]$

2. 理解第二个递推公式