【300.最长递增子序列】思路dp[i]的定义本题中正确定义dp数组的含义十分重要。dp[i]表示i之前包括i的以nums[i]结尾的最长递增子序列的长度为什么一定表示 “以nums[i]结尾的最长递增子序” 因为我们在做递增比较的时候如果比较 nums[j] 和 nums[i] 的大小那么两个递增子序列一定分别以nums[j]为结尾 和 nums[i]为结尾 要不然这个比较就没有意义了不是尾部元素的比较那么如何算递增呢。状态转移方程位置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的最大值。dp[i]的初始化每一个i对应的dp[i]即最长递增子序列起始大小至少都是1.确定遍历顺序dp[i] 是有0到i-1各个位置的最长递增子序列 推导而来那么遍历i一定是从前向后遍历。j其实就是遍历0到i-1那么是从前到后还是从后到前遍历都无所谓只要吧 0 到 i-1 的元素都遍历了就行了。 所以默认习惯从前向后遍历。遍历i的循环在外层遍历j则在内层代码如下for(inti1;inums.size();i){for(intj0;ji;j){if(nums[i]nums[j])dp[i]max(dp[i],dp[j]1);}if(dp[i]result)resultdp[i];// 取长的子序列}举例推导dp数组解法classSolution{public:intlengthOfLIS(vectorintnums){if(nums.size()1)returnnums.size();vectorintdp(nums.size(),1);// dp[i]表示是以nums[i]结尾的最长递增子序列的长度intresult1;for(inti1;inums.size();i){for(intj0;ji;j){if(nums[i]nums[j])dp[i]max(dp[i],dp[j]1);}if(dp[i]result)resultdp[i];}returnresult;}};【674.最长连续递增子序列】思路求连续只需要从低到高一层遍历即可classSolution{public:intfindLengthOfLCIS(vectorintnums){if(nums.size()1)returnnums.size();vectorintdp(nums.size(),1);// dp[i]表示以nums[i]结尾的最长连续递增子序列intresult1;for(inti1;inums.size();i){if(nums[i]nums[i-1])dp[i]dp[i-1]1;if(resultdp[i])resultdp[i];}returnresult;}};【718.最长重复子数组】思路本题是动规解决的经典题目需要想到用二维数组可以记录两个字符串的所有比较情况这样就比较好推递推公式了。 动规五部曲分析如下确定dp数组dp table以及下标的含义dp[i] [j] 以下标i - 1为结尾的A和以下标j - 1为结尾的B最长重复子数组长度为dp[i] [j]。 特别注意 “以下标i - 1为结尾的A” 标明一定是 以A[i-1]为结尾的字符串 此时应该提出问题那dp[0] [0]是什么含义呢总不能是以下标-1为结尾的A数组吧。其实dp[i] [j]的定义也就决定着我们在遍历dp[i] [j]的时候 i 和 j 都要从1开始。那还有问题我就定义dp[i] [j]为以下标 i 为结尾的A和以下标 j 为结尾的B最长重复子数组长度。不行么行倒是行 但实现起来就麻烦一点需要单独处理初始化部分在本题解下面的拓展内容里给出了第二种 dp数组的定义方式所对应的代码和讲解比较一下就了解了。确定递推公式根据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数组如何初始化根据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正好符合递推公式逐步累加起来。确定遍历顺序外层for循环遍历A内层for循环遍历B。那又有同学问了外层for循环遍历B内层for循环遍历A。不行么也行一样的这里就用外层for循环遍历A内层for循环遍历B了。同时题目要求长度最长的子数组的长度。所以在遍历的时候顺便把dp[i] [j]的最大值记录下来。代码如下for(inti1;inums1.size();i){for(intj1;jnums2.size();j){if(nums1[i-1]nums2[j-1]){dp[i][j]dp[i-1][j-1]1;}if(dp[i][j]result)resultdp[i][j];}}举例推导dp数组// 二维dp数组解法classSolution{public:intfindLength(vectorintnums1,vectorintnums2){vectorvectorintdp(nums1.size()1,vectorint(nums2.size()1,0));// dp[i] [j] 以下标i - 1为结尾的A和以下标j - 1为结尾的B最长重复子数组长度为dp[i] [j]。 **特别注意** “以下标i - 1为结尾的A” 标明一定是 以A[i-1]为结尾的字符串 intresult0;for(inti1;inums1.size();i){for(intj1;jnums2.size();j){if(nums1[i-1]nums2[j-1]){dp[i][j]dp[i-1][j-1]1;}if(dp[i][j]result)resultdp[i][j];}}returnresult;}};可以看出dp[i] [j]都是由dp[i - 1] [j - 1]推出。那么压缩为一维数组也就是dp[j]都是由dp[j - 1]推出。也就是相当于可以把上一层dp[i - 1] [j]拷贝到下一层dp[i] [j]来继续用。此时遍历B数组的时候就要从后向前遍历这样避免重复覆盖。降维成一维数组后dp[j] dp[j‑1]1需要用上一行 (i‑1) 的旧dp[j‑1]。逆序从大到小dp[j‑1]还没被本轮 i 修改保留旧值 ✅正序从小到大dp[j‑1]已经被本轮 i 更新成新值数据污染 ❌原理和 0‑1 背包一维逆序是同一个道理。// 一维dp数组解法classSolution{public:intfindLength(vectorintnums1,vectorintnums2){vectorintdp(nums2.size()1,0);intresult0;for(inti1;inums1.size();i){for(intjnums2.size();j1;j--){if(nums1[i-1]nums2[j-1])dp[j]dp[j-1]1;elsedp[j]0;if(dp[j]result)resultdp[j];}}returnresult;}};拓展前面讲了 dp数组为什么定义以下标i - 1为结尾的A和以下标j - 1为结尾的B最长重复子数组长度为dp[i] [j]。我就定义dp[i] [j]为 以下标i为结尾的A和以下标j 为结尾的B最长重复子数组长度。不行么也可以就是实现起来麻烦一些。如果定义 dp[i] [j]为 以下标i为结尾的A和以下标j 为结尾的B那么 第一行和第一列毕竟要进行初始化如果nums1[i] 与 nums2[0] 相同的话对应的 dp[i] [0]就要初始为1 因为此时最长重复子数组为1。 nums2[j] 与 nums1[0]相同的话同理。所以代码如下// 版本三classSolution{public:intfindLength(vectorintnums1,vectorintnums2){vectorvectorintdp(nums1.size()1,vectorint(nums2.size()1,0));intresult0;// 要对第一行第一列经行初始化for(inti0;inums1.size();i)if(nums1[i]nums2[0])dp[i][0]1;for(intj0;jnums2.size();j)if(nums1[0]nums2[j])dp[0][j]1;for(inti0;inums1.size();i){for(intj0;jnums2.size();j){if(nums1[i]nums2[j]i0j0){// 防止 i-1 出现负数dp[i][j]dp[i-1][j-1]1;}if(dp[i][j]result)resultdp[i][j];}}returnresult;}};会发现 这种写法 一定要多写一段初始化的过程。而且为了让if (dp[i][j] result) result dp[i][j];收集到全部结果两层for训练一定从0开始遍历这样需要加上 i 0 j 0的判断。