代码随想录算法训练营第五十二天 | LeetCode 300. 最长递增子序列、674. 最长连续递增序列、718. 最长重复子数组
1. LeetCode 300. 最长递增子序列
1.1 思路
- 本题是属于子序列系列，同样是动态规划解决的经典的一系列问题。
- dp 数组及其下标的含义：dp[i] 表示以 nums[i] 为结尾的最长递增子序列的长度为 dp[i]
- 递推公式：设 j 在 [0,i)之间，当 nums[i]>nums[j] 时，nums[i] 可以接在 nums[j] 之后（严格递增时），就相当于 nums[i] 是直接加在 dp[j] 原来的递增子序列后的，此时 dp[i]=dp[j]+1；当 nums[i]<=nums[j] 时，nums[i] 不可以接在 nums[j] 之后，就 dp[i]=dp[i]。因此 dp[i]=Math.max（dp[i]，dp[j]+1）
- dp 数组的初始化：dp[i] 至少都是 1，意思是至少包含 nums[i]
- 遍历顺序：这里都依赖前面的元素，因此 i 一定是从左到右遍历，for（int i=1；i<nums.length；i++）为什么从 1 开始？因为 dp[0]=1 没必要求了，肯定为 1。for（int j=0；j<i；j++）遍历所有 nums[j] 的情况和 nums[i] 做比较，j 从前往后还是从后往前呢？其实都可以，只要把 [0,i) 之间都遍历了就可以了。if（nums[i]>nums[j]）dp[i]=Math.max（dp[i]，dp[j]+1）
- 最终结果存在哪呢？是在 dp 数组的最大值，就遍历 dp 数组，result=Math.max（dp[i]，result），最终返回 result 即可
- 打印 dp 数组：用于 debug
1.2 代码
class Solution { public int lengthOfLIS(int[] nums) { int[] dp = new int[nums.length]; int res = 0; Arrays.fill(dp, 1); for (int i = 1; i < dp.length; i++) { for (int j = 0; j < i; j++) { if (nums[i] > nums[j]) { dp[i] = Math.max(dp[i], dp[j] + 1); } res = Math.max(res, dp[i]); } } return res; } }
2. LeetCode 674. 最长连续递增序列
2.1 思路
- 本题和300. 最长递增子序列的区别就在于要求连续。
- dp 数组及其下标的含义：dp 表示以 i 为结尾的最长连续递增子序列为 dp[i]
- 递推公式：因为本题要求连续，就不需要比较前面所有的元素了，直接比较 nums[i] 和 nums[i-1]，如果 nums[i]>nums[i-1] 就 dp[i]=dp[i-1]+1，就相当于 nums[i] 直接接在了 dp[i-1] 后面了，因此就 dp[i-1]+1
- dp 数组的初始化：dp 数组全部都初始化为 1，因为每个元素本身就是连续的，就是 1
- 遍历顺序：因为 i 依赖 i-1，因此是从前往后遍历，for（int i=1；i<nums.length；i++）这里为什么从 1 开始？因为 dp[0] 一定是 1。
- 最终结果在哪里？是在 dp 数组的最大值中，因此遍历 dp 数组，result=Math.max（dp[i]，result），最终返回 result
- 打印 dp 数组：用于 debug
2.2 代码
/** * 1.dp[i] 代表当前下标最大连续值 * 2.递推公式 if（nums[i+1]>nums[i]） dp[i+1] = dp[i]+1 * 3.初始化 都为1 * 4.遍历方向，从其那往后 * 5.结果推导 。。。。 * @param nums * @return */ public static int findLengthOfLCIS(int[] nums) { int[] dp = new int[nums.length]; for (int i = 0; i < dp.length; i++) { dp[i] = 1; } int res = 1; //可以注意到，這邊的 i 是從 0 開始，所以會出現和卡哥的C++ code有差異的地方，在一些地方會看到有 i + 1 的偏移。 for (int i = 0; i < nums.length - 1; i++) { if (nums[i + 1] > nums[i]) { dp[i + 1] = dp[i] + 1; } res = res > dp[i + 1] ? res : dp[i + 1]; } return res; }
3. LeetCode 718. 最长重复子数组
3.1 思路
- 求两个数组的最长重复子数组的长度，其实就是求最长连续子序列。
- dp 数组及其下标的含义：我们用一个二维 dp 数组保存我们两个数组比较的状态。dp[i][j] 表示的是最长重复子数组，第一个数组到 i，第二个数组到 j，最长重复子数组为 dp[i][j]。即 dp[i][j] 表示以 i-1 为结尾的数组 1 和以 j-1 为结尾的数组 2，最长重复子数组长度为 dp[i][j]。为什么不以 i 和 j 为结尾呢？那么定义是为了简洁
- 递推公式：if（nums1[i-1]==nums2[j-1]）就相当于找到两个数组中相等的元素了 dp[i][j]=dp[i-1][j-1]+1，为什么是从 i-1,j-1 这里+1 呢？因为我们是比较两个数组中的元素是否相同，如果相同就要两个数组一起往后退一格，一起看后面元素的状态，从这个
- dp 数组的初始化：dp[i][0] 和 dp[0][j] 就是第一列和第一行都是没有意义的状态，因为我们要用到 i-1 和 j-1，因此应该初始化为 0，因为 dp 数组是在前一个状态+1，这里没有意义就不要初始化为 1 了。其余位置会被递推公式覆盖，就可以不用初始化，默认为 0 即可
- 遍历顺序：肯定是两层 for 循环，先遍历数组 1 还是数组 2 呢？其实都可以。这里 for（int i=1；i<=nums1.length；i++）for（int j=1；j<=nums2.length；j++）因为 0 这一行和列没有意义，直接都从 1 开始。为什么取等于号呢？我们的 dp 数组的长度是 nums1 和 nums2 的长度加 1 的，而我们比较的时候是比较 nums[i-1] 和 nums[j-1]，因此不会越界。
- 最终结果存在哪？不是在最后面的位置的，因此要遍历二维数组，找到最大值，因此在两层 for 循环遍历的时候就记录最大值了，再第二层 for 循环中最后 if（dp[i][j]>result）result=dp[i][j]
- 打印 dp 数组：用于 debug
- 解释：为什么不定义 i 和 j 为结尾的子序列呢？如果这样的话，第一列和第一行就要遍历统计，如果对应位置相等了，就要初始化为 1 了，就比较麻烦了
3.2 代码
// 版本一 class Solution { public int findLength(int[] nums1, int[] nums2) { int result = 0; int[][] dp = new int[nums1.length + 1][nums2.length + 1]; for (int i = 1; i < nums1.length + 1; i++) { for (int j = 1; j < nums2.length + 1; j++) { if (nums1[i - 1] == nums2[j - 1]) { dp[i][j] = dp[i - 1][j - 1] + 1; result = Math.max(result, dp[i][j]); } } } return result; } }
