day42 代码随想录算法训练营 动态规划专题10
1 今日打卡
最长连续递增序列 674. 最长连续递增序列 - 力扣（LeetCode）
最长递增子序列 300. 最长递增子序列 - 力扣（LeetCode）
最长重复子数组 718. 最长重复子数组 - 力扣（LeetCode）
2 dp五部曲
确定dp数组及其下标的含义
状态转移方程
初始化
遍历顺序
手动模拟
3 最长连续递增序列
3.1 思路
第一步：
dp[i] 表示：以数组中第 i 个元素（nums[i]）结尾的最长连续递增子序列的长度。
为什么要定义 “以nums[i]结尾”？因为连续递增的特性要求子序列必须是连续的，nums[i] 能否接在 nums[i-1] 后面，只需要比较两者的大小，而 “以i结尾” 的定义能让我们通过前一个位置的结果推导出当前位置的结果。
第二步：
核心逻辑：如果当前元素 nums[i] 大于前一个元素 nums[i-1]，说明可以把 nums[i] 接在以 nums[i-1] 结尾的递增子序列后面，此时 dp[i] = dp[i-1] + 1；
如果 nums[i] <= nums[i-1]，说明无法形成连续递增，以 nums[i] 结尾的最长连续递增子序列只能是它自己，因此 dp[i] 保持初始化的 1 即可。
第三步：
每个元素自身可以构成一个长度为 1 的递增子序列，因此需要将 dp 数组的所有元素初始化为 1（Arrays.fill(dp, 1)）；
同时初始化结果变量 res = 1，因为数组至少有一个元素，最长长度不会小于 1。
第四步：
因为 dp[i] 的值依赖于 dp[i-1]，所以需要从左到右遍历数组（i 从 1 开始，到 len-1 结束）；
遍历过程中，每计算出一个 dp[i]，就和 res 比较，更新 res 为当前最大值。
第五步：
以示例数组 nums = [1,3,5,4,7] 为例：
初始化：dp = [1,1,1,1,1]，res = 1；
i=1（nums[1]=3 > nums[0]=1）：dp[1] = 1+1=2，res 更新为 2；
i=2（nums[2]=5 > nums[1]=3）：dp[2] = 2+1=3，res 更新为 3；
i=3（nums[3]=4 < nums[2]=5）：dp[3] 保持 1，res 仍为 3；
i=4（nums[4]=7 > nums[3]=4）：dp[4] = 1+1=2，res 还是 3；
最终返回 res=3，对应最长连续递增子序列 [1,3,5]。
3.2 实现代码
import java.util.Arrays; class Solution { public int findLengthOfLCIS(int[] nums) { // 1. 处理边界情况：如果数组为空，直接返回0 if (nums == null || nums.length == 0) { return 0; } // 获取数组长度 int len = nums.length; // 2. dp数组定义：dp[i]表示以nums[i]结尾的最长连续递增子序列的长度 int[] dp = new int[len]; // 3. 初始化：每个元素自身是长度为1的子序列，所以全部填充为1 Arrays.fill(dp, 1); // 初始化结果变量，最小为1（数组至少有一个元素） int res = 1; // 4. 遍历顺序：从左到右遍历，i从1开始（因为要比较i-1） for (int i = 1; i < len; i++) { // 状态转移方程：如果当前元素大于前一个元素，说明可以接在前面的子序列后 if (nums[i] > nums[i - 1]) { dp[i] = dp[i - 1] + 1; } // 每次更新当前的最大长度 if (dp[i] > res) { res = dp[i]; } } // 5. 返回最长连续递增子序列的长度 return res; } }4 最长递增子序列
4.1 思路
第一步：
dp[i] 表示：以数组中第 i 个元素（nums[i]）结尾的最长递增子序列的长度。
这个定义和 LCIS 一致，但因为 “不要求连续”，dp[i] 不再只依赖 dp[i-1]，而是需要遍历 i 之前的所有元素 j（j < i）来推导。
第二步：
核心逻辑：对于每个 i，遍历所有 j < i，如果 nums[i] > nums[j]，说明 nums[i] 可以接在以 nums[j] 结尾的递增子序列后面，此时候选长度为 dp[j] + 1；
我们需要在所有满足 nums[i] > nums[j] 的 dp[j] 中找到最大值，再加 1 作为 dp[i]；如果没有任何 j 满足 nums[i] > nums[j]，则 dp[i] 保持初始化的 1（自身构成子序列）。
公式总结：
plaintext
dp[i] = max(dp[j] + 1) （其中 j < i 且 nums[i] > nums[j]）
若没有满足条件的 j → dp[i] = 1
第三步：
每个元素自身可以构成一个长度为 1 的递增子序列，因此 dp 数组所有元素初始化为 1（Arrays.fill(dp, 1)）；
结果变量 res 初始化为 0，遍历过程中不断更新为 dp 数组的最大值。
第四步：
外层循环：i 从 1 到 len-1（逐个处理每个结尾元素）；
内层循环：j 从 0 到 i-1（遍历 i 之前的所有元素，寻找能接在后面的最长子序列）；
先通过内层循环算出 dp[i]，再用 dp[i] 更新 res，确保 res 始终是当前最长长度。
第五步：
以示例数组 nums = [10,9,2,5,3,7,101,18] 为例：
初始化：dp = [1,1,1,1,1,1,1,1]，res = 0；
i=1（nums [1]=9 < nums [0]=10）：无满足条件的 j，dp[1]=1，res=1；
i=2（nums[2]=2 < 10/9）：dp[2]=1，res=1；
i=3（nums[3]=5 > nums[2]=2）：dp[3] = dp[2]+1=2，res=2；
i=4（nums[4]=3 > nums[2]=2）：dp[4] = dp[2]+1=2，res 仍为 2；
i=5（nums [5]=7 > 2/5/3）：最大 dp[j]=2，dp[5]=3，res=3；
i=6（nums [6]=101 > 所有前序元素）：最大 dp[j]=3，dp[6]=4，res=4；
i=7（nums [7]=18 > 2/5/3/7）：最大 dp[j]=3，dp[7]=4，res 仍为 4；
最终返回 res=4，对应最长递增子序列（如 [2,5,7,101] 或 [2,3,7,18]）。
4.2 实现代码
import java.util.Arrays; class Solution { public int lengthOfLIS(int[] nums) { // 获取数组长度 int len = nums.length; // 边界情况：长度为1返回1 if (len == 1) { return 1; } // 1. dp数组定义：dp[i]表示以nums[i]结尾的最长递增子序列的长度 int[] dp = new int[len]; // 2. 初始化：每个元素自身是长度为1的子序列，全部填充为1 Arrays.fill(dp, 1); // 初始化结果变量，记录全局最长长度 int res = 0; // 3. 遍历顺序：外层i从1开始（逐个处理每个结尾元素） for (int i = 1; i < len; i++) { // 记录i之前能接在nums[i]前面的最长子序列长度 int max = 0; // 内层j遍历0到i-1，寻找所有nums[j] < nums[i]的情况 for (int j = 0; j < i; j++) { // 如果nums[i] > nums[j]，且dp[j]是当前找到的最大值 if (nums[i] > nums[j] && dp[j] > max) { max = dp[j]; } } // 4. 状态转移：dp[i] = 能接的最长子序列长度 + 1（自身） dp[i] = max + 1; // 更新全局最长长度 if (dp[i] > res) { res = dp[i]; } } // 5. 返回最长递增子序列的长度 return res; } }5 最长重复子数组
5.1 思路
第一步：
定义 dp[i][j]：以 nums1[i-1] 为最后一个元素、以 nums2[j-1] 为最后一个元素的最长公共连续子数组的长度。
为什么用 i-1/j-1？
若直接用 dp[i][j] 对应 nums1[i]/nums2[j]，则需要单独处理 i=0 或 j=0 的边界（比如数组第一个元素匹配时）；而 dp[i][j] 对应 i-1/j-1 可以让 dp[0][*] 和 dp[*][0] 都为 0（空数组与任意数组的公共子数组长度为 0），简化初始化逻辑。
第二步：
核心逻辑：子数组是连续的，只有当前元素匹配时，才能延续前一个位置的公共长度；不匹配则长度归 0。
若 nums1[i-1] == nums2[j-1]：当前元素匹配，公共子数组长度 = 前一个位置的公共长度 + 1 → dp[i][j] = dp[i-1][j-1] + 1；
若 nums1[i-1] != nums2[j-1]：当前元素不匹配，以这两个元素结尾的公共子数组中断，长度为 0 → dp[i][j] = 0（代码中未显式写这行，因为数组默认初始化值就是 0，效果等价）。
第三步：
dp 是 (len1+1) × (len2+1) 的二维数组，所有元素默认初始化为 0；
dp[0][j] = 0（nums1 取前 0 个元素，即空数组，和 nums2 前 j 个元素无公共子数组）；
dp[i][0] = 0（nums2 取前 0 个元素，同理无公共子数组）；
结果变量 res = 0，用于记录遍历过程中出现的最大公共子数组长度。
第四步：
因为 dp[i][j] 的值依赖于左上角的 dp[i-1][j-1]，所以必须按从上到下、从左到右的顺序遍历：
外层循环：i 从 1 到 len1（遍历 nums1 的每个元素，对应 nums1[i-1]）；
内层循环：j 从 1 到 len2（遍历 nums2 的每个元素，对应 nums2[j-1]）；
每计算完一个 dp[i][j]，就和 res 比较，更新 res 为当前最大值。
第五步：
以 nums1 = [1,2,3,2,1]、nums2 = [3,2,1,4,7] 为例：
初始化：dp 数组全为 0，res=0；
i=1（nums1 [0]=1）：
j=1（nums2 [0]=3）→ 不匹配 → dp [1][1]=0，res=0；
j=2（nums2 [1]=2）→ 不匹配 → dp [1][2]=0，res=0；
j=3（nums2 [2]=1）→ 匹配 → dp [1][3] = dp [0][2]+1=1，res=1；
i=3（nums1 [2]=3）：
j=1（nums2 [0]=3）→ 匹配 → dp [3][1] = dp [2][0]+1=1，res=1；
i=4（nums1 [3]=2）：
j=2（nums2 [1]=2）→ 匹配 → dp [4][2] = dp [3][1]+1=2，res=2；
i=5（nums1 [4]=1）：
j=3（nums2 [2]=1）→ 匹配 → dp [5][3] = dp [4][2]+1=3，res=3；
最终返回 res=3，对应最长公共子数组 [3,2,1]。
5.2 实现代码
class Solution { public int findLength(int[] nums1, int[] nums2) { // 获取两个数组的长度 int len1 = nums1.length, len2 = nums2.length; // 1. 定义dp数组：dp[i][j]表示以nums1[i-1]和nums2[j-1]结尾的最长公共子数组长度 // 维度为(len1+1)x(len2+1)，默认初始值为0，无需额外初始化 int[][] dp = new int[len1 + 1][len2 + 1]; // 记录全局最长公共子数组的长度，初始为0 int res = 0; // 2. 遍历顺序：从上到下、从左到右（i从1开始对应nums1[i-1]） for(int i = 1; i <= len1; i++) { for(int j = 1; j <= len2; j++) { // 3. 状态转移方程：当前元素匹配时，延续前一个位置的长度+1 if(nums1[i-1] == nums2[j-1]) { // 修正原代码的nums[i]/nums[j]笔误 dp[i][j] = dp[i-1][j-1] + 1; } // 4. 更新全局最大值：只要当前dp[i][j]更大，就更新res if(dp[i][j] > res) { res = dp[i][j]; } } } // 5. 返回最长公共子数组的长度 return res; } }
