摘要
如果答案在
dp数组中的位置不是固定的，可以在dp数组的更新过程中记录可能的答案，简化代码，例如今天的三道题，都可以在每次更新dp数组后来记录最大值。通过
dp数组的定义中的下标偏移（+1或-1等等），在dp数组中添加初始行和初始列，可以简化初始化逻辑和下标越界判断。
LeetCode300 最长递增子序列
- 初见题目的想法：每个数字都有可能作为最长递增子序列的结束，且以
nums[i]作为结束的递增子序列的最小长度是1，dp[i]是以nums[i]作为结束的递增子序列的最长长度，假设j < i，根据dp数组的定义，如果num[j] < nums[i]，nums[i]可以接在以nums[j]为结尾的序列上，则dp[i] = dp[j] + 1；如果nums[j] >= nums[i]，则nums[i]不能接在以nums[j]结尾的序列上。由此得到递推公式：
题解代码如下
class Solution {
public:
int lengthOfLIS(vector<int>& nums) {
vector<int> dp(nums.size(), 1);
for (int i = 0; i < nums.size(); i++) {
for (int j = 0; j < i; j++) {
if (nums[j] < nums[i]) dp[i] = max(dp[i], dp[j] + 1);
}
}
int res = INT_MIN;
for (int i = 0; i < nums.size(); i++)
res = max(res, dp[i]);
return res;
}
};
- 还是按步骤来思考如何使用动态规划来解决这道题
-
dp数组及下标的含义：dp[i]是以nums[i]作为结束的递增子序列的最长长度。 - 确定递推公式，假设
j < i，根据dp数组的定义- 如果
nums[j] < nums[i]，则nums[i]能接在以nums[j]为结尾的序列后，假设dp[j]是已知的，那么。
- 如果
nums[j] >= nums[i]，则nums[i]不能接在以nums[j]为结尾的序列后，此时不需要更新dp数组。
- 如果
- 确定如何初始化
dp数组，根据dp数组的定义，以nums[i]结尾的递增序列的长度至少是1，即序列至少包含nums[i]自身，所以dp数组所有的值初始化为1。 - 遍历顺序：
dp[i]是由j < i的dp[j]推导而来的，所以应该从小到大遍历i；而对于选定了i之后，只需要遍历所有的，
j从小到大还是从大到小都可以。
题解代码如下，记录最大值的操作可以放在dp数组的更新中，简化代码
class Solution {
public:
int lengthOfLIS(vector<int>& nums) {
vector<int> dp(nums.size(), 1);
int res = INT_MIN;
for (int i = 0; i < nums.size(); i++) {
for (int j = 0; j < i; j++) {
if (nums[j] < nums[i]) dp[i] = max(dp[i], dp[j] + 1);
}
res = max(res, dp[i]);
}
return res;
}
};
LeetCode674 最长连续递增子序列
- 初见题目的想法：其实这就是在上一题的基础上对
j做了限制，因为要保证递增子序列中的元素在原序列中连续，所以nums[i]只能接在以nums[i - 1]，为结尾的子序列上，那么根据dp数组的定义，对于j < i，能取的j其实只有i - 1了。
题解代码如下
class Solution {
public:
int findLengthOfLCIS(vector<int>& nums) {
vector<int> dp(nums.size(), 1);
int res = 1;
for (int i = 1; i < nums.size(); i++) {
if (nums[i - 1] < nums[i]) dp[i] = max(dp[i], dp[i - 1] + 1);
res = max(res, dp[i]);
}
return res;
}
};
其实max(dp[i], dp[i - 1] + 1)也没有必要，因为dp[i]只可能被更新一次，如果dp[i]被更新，那肯定比初始的值要大。
class Solution {
public:
int findLengthOfLCIS(vector<int>& nums) {
vector<int> dp(nums.size(), 1);
int res = 1;
for (int i = 1; i < nums.size(); i++) {
if (nums[i - 1] < nums[i]) dp[i] = dp[i - 1] + 1;
res = max(res, dp[i]);
}
return res;
}
};
- 然后还是按动规的步骤来分析这道题
-
dp数组及数组下标的含义：dp[i]表示的是以nums[i]为结尾的递增子序列的最长长度。 - 递推公式：因为限制了连续，所以
dp[i]要么由dp[i-1]推导而来，要么保持初始值。所以 - 遍历顺序：
i从小到大遍历，因为dp[i]依赖于dp[i-1]。
LeetCode718 最长重复子数组
-
dp数组及数组下标的含义：dp[i][j]的含义是，以nums1[i - 1]为结尾的nums1的子数组和以nums2[j - 1]为结尾的nums2的子数组，两者的最长重复部分的长度为dp[i][j]。这样定义dp数组可以为初始化和实现代码提供便利。另外，要注意的是，子数组是连续的子序列。怎么体现“连续”呢？ - 确定递推公式：
- 如果
nums1[i-1] == nums2[j-1]，那么说明nums1[i-1]可以接在nums1[i-2]为结尾的nums1的子数组后，nums[j-1]可以接在nums[j-2]为结尾的子数组后，所以dp[i][j]应该由dp[i-1][j-1]推导而来。 - 如果
nums1[i-1]接在nums1[i-2]为结尾的nums1的子数组后，nums[j-1]可以接在nums[j-2]为结尾的子数组后，且nums1[i-1] == nums[j-1]，那么重复子序列的长度就可以+1，即 - 在同一次比较中，
i和j应该是同进同退的。如果在同一次比较中取比较i和j-1，或者比较i-1和j，就不算是同一次比较了，因为这样相当于考虑另外的子数组的可能。实际上i和j不同进同退的话也很难写出逻辑清晰的实现代码。这或许体现出了“连续”子序列，因为如果i和j不同进同退，就可能导致某一方的子序列是“断开”的。这样说可能还是太抽象了，毕竟dp数组的定义完全没有提到连续，只能通过递推公式去控制“连续”。
- 如果
- 确定
dp数组如何初始化，dp数组的定义为dp数组的初始化提供了方便，-
dp[i][0]和dp[0][j]的含义实际上没有意义，因为会出现-1的下标，那应该初始化成什么值呢，只有初始化成0是不影响之后的dp数组的计算的，因为重复子序列的长度肯定是从0开始累加的。 - 实际上，这相当于用额外空间简化了初始化过程，也简化了边界条件的判断。
-
- 确定遍历顺序，
dp[i][j]依赖于dp[i-1][j-1]，所以i和j都应该从小到大遍历。
题解代码如下
class Solution {
public:
int findLength(vector<int>& nums1, vector<int>& nums2) {
vector<vector<int>> dp(nums1.size() + 1, vector<int>(nums2.size() + 1, 0));
int res = 0;
for (int i = 1; i <= nums1.size(); i++) {
for (int j = 1; j <= nums2.size(); j++) {
if (nums1[i - 1] == nums2[j - 1]) {
dp[i][j] = dp[i - 1][j - 1] + 1;
}
res = max(res, dp[i][j]);
}
}
return res;
}
};
以nums1 = [1,2,3,2,1]; nums2 = [3,2,1,4,7]为例，模拟dp数组的更新过程。
- 那么，还是回到没解决的问题上来，怎么体现“连续”？
-
dp[i][j]表示以nums1[i-1]结尾的nums1的子序列和以nums[j-1]结尾的nums2的子序列，两者的最长重复部分的长度为dp[i][j]。回顾dp数组的定义，这可没提到“连续”。 - 我目前的理解是，“连续”体现在递推公式和
dp数组的更新过程中，因为以上分析没有考虑nums1[i-1] != nums2[j-1]的情况，也就是nums1[i-1]和nums2[i-1]接不上的情况，只有能接上的时候才更新dp数组，那其实也就只考虑了连续的情况，隐式地忽略了那些不连续的情况。 - 如果不要求连续的话，假设
nums1[i-1] != nums2[j-1]，可以更新dp数组吗？根据经验，可能会这样来更新：dp[i][j]=dp[i-1][j-1]，根据dp数组的定义来理解就是nums1[i-1]和nums[j-1]接不上了，但是之前的以nums1[i-1-1]为结尾和nums2[j-1-1]为结尾的公共子数组是可以的。但是，这就违反了dp数组的定义，因为我们明确要求的是以nums1[i-1]结尾和以nums2[j-1]结尾，而不是“尝试到”nums1[i-1]和nums[j-1] - 所以，
dp数组的定义其实也暗含了"连续"，因为dp数组的定义明确指定了子序列以什么作为结尾，这一点和第二天要写的 1143. 最长公共子序列 - 力扣（Leetcode）是不一样的！
-
dp 数组定义的问题
- 如果这样来定义
dp数组：dp[i][j]的含义是，以nums1[i]为结尾的nums1的子数组和以nums2[j]为结尾的nums2的子数组，两者的最长重复部分的长度为dp[i][j]。会怎么样呢？ - 分析的过程就不赘述了，只是从
dp数组的下标到nums1和nums2的数组下标的对应关系变化了，dp[i][j]对应的不再是nums1[i-1]和nums2[j-1]，而是直接对应nums[i]和nums[j]。 - 初始化也有变化，如果
nums1[i]与nums2[0]相同的话，对应的dp[i][0]就要初始化为1， 因为此时最长重复子数组为1。nums2[j]与nums1[0]相同的话，同理。- 相当于假设了
nums1[i]与nums2[0]相等，nums2[j]与nums1[0]相等，因为在dp数组的更新过程中，由于下标不能出现负数，不会再更新dp[i][0]和dp[0][j]。所以这样定义dp数组似乎也不算很直观。
- 相当于假设了
- 由于下标不能出现负数，还要添加边界条件判断。
使用这样的定义的dp数组的实现代码如下
class Solution {
public:
int findLength(vector<int>& nums1, vector<int>& nums2) {
vector<vector<int>> dp (nums1.size() + 1, vector<int>(nums2.size() + 1, 0));
// 要对第一行，第一列进行初始化
for (int i = 0; i < nums1.size(); i++) if (nums1[i] == nums2[0]) dp[i][0] = 1;
for (int j = 0; j < nums2.size(); j++) if (nums1[0] == nums2[j]) dp[0][j] = 1;
int res = 0;
for (int i = 0; i < nums1.size(); i++) {
for (int j = 0; j < nums2.size(); j++) {
if (nums1[i] == nums2[j] && i && j) { // 防止 i-1,j-1 出现负数
dp[i][j] = dp[i - 1][j - 1] + 1;
}
res = max(res, dp[i][j]);
}
}
return res;
}
};
- 可见，通过
dp数组的定义中的下标偏移，在dp数组中添加初始行和初始列，可以简化初始化逻辑和下标越界判断。
