【代码随想录Day41】动态规划Part10

300.最长递增子序列

题目链接/文章讲解：代码随想录
视频讲解：动态规划之子序列问题，元素不连续！| LeetCode：300.最长递增子序列_哔哩哔哩_bilibili

public int lengthOfLIS(int[] nums) {// 获取数组的长度int n = nums.length;// 创建一个用于存储以每个元素结尾的最长递增子序列的长度的数组int[] dp = new int[n + 1];// 初始化dp数组，默认每个位置的最长递增子序列长度为1for (int j = 0; j <= n; j++) {dp[j] = 1;}// 初始化结果变量，记录最长递增子序列的最大长度int result = 1;// 遍历每个元素for (int i = 1; i < nums.length; i++) {// 对于当前元素，遍历其之前的所有元素for (int j = 0; j < i; j++) {// 如果当前元素大于之前的元素，可能形成递增子序列if (nums[i] > nums[j]) {// 更新dp[i]为以nums[i]结尾的最长递增子序列长度dp[i] = Math.max(dp[i], dp[j] + 1);}}// 更新结果，保持最长递增子序列的最大长度result = Math.max(result, dp[i]);}// 返回最长递增子序列的长度return result;
}

674. 最长连续递增序列

题目链接/文章讲解：代码随想录
视频讲解：动态规划之子序列问题，重点在于连续！| LeetCode：674.最长连续递增序列_哔哩哔哩_bilibili

class Solution {public int findLengthOfLCIS(int[] nums) {// 获取输入数组的长度int n = nums.length;// 创建一个 dp 数组，用于存储以每个元素结尾的 LCIS（最长连续递增子序列）的长度int[] dp = new int[n];// 初始化第一个元素的 LCIS 长度为 1dp[0] = 1;// 用于记录当前找到的最长连续递增子序列的长度int result = 1;// 从第二个元素开始遍历数组for (int i = 1; i < n; i++) {// 如果当前元素大于前一个元素，说明可以延续递增序列if (nums[i] > nums[i - 1]) {// 更新 dp[i] 为前一个元素的 dp 值加 1dp[i] = Math.max(dp[i], dp[i - 1] + 1);} else {// 如果当前元素不大于前一个元素，重新开始新的 LCIS，长度为 1dp[i] = 1;}// 更新 result 为当前找到的最大值result = Math.max(result, dp[i]);}// 返回最长连续递增子序列的长度return result;}
}

718. 最长重复子数组

题目链接/文章讲解：代码随想录
视频讲解：动态规划之子序列问题，想清楚 DP 数组的定义 | LeetCode：718.最长重复子数组_哔哩哔哩_bilibili

class Solution {public int findLength(int[] nums1, int[] nums2) {// 获取两个数组的长度int m = nums1.length;int n = nums2.length;// 创建一个二维数组 dp，用于存储公共子数组的长度// dp[i][j] 表示 nums1 的前 i 个元素和 nums2 的前 j 个元素的公共子数组的长度int[][] dp = new int[m + 1][n + 1];// 用于记录找到的最大公共子数组的长度int result = 0;// 遍历 nums1 和 nums2 的每个元素for (int i = 1; i <= m; i++) {for (int j = 1; j <= n; j++) {// 如果 nums1 的第 i-1 个元素等于 nums2 的第 j-1 个元素if (nums1[i - 1] == nums2[j - 1]) {// 更新 dp[i][j]，表示当前公共子数组长度// dp[i][j] 由 dp[i-1][j-1] 加 1 得到dp[i][j] = Math.max(dp[i][j], dp[i - 1][j - 1] + 1);}// 更新 result，记录当前找到的最大公共子数组长度result = Math.max(result, dp[i][j]);}}// 返回找到的最大公共子数组长度return result;}
}