当前位置：首页 > news >正文

代码随想录算法训练营day43｜动态规划part10

news 来源：原创 2024/9/21 20:27:25

第一题：300. Longest Increasing Subsequence

class Solution {public int lengthOfLIS(int[] nums) {if (nums.length <= 1) return nums.length;int[] dp = new int[nums.length];int res = 1;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;}
}

第二题： 674. Longest Continuous Increasing Subsequence

动态规划：

 /*** 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;}

动态规划状态压缩

class Solution {public int findLengthOfLCIS(int[] nums) {// 记录以 前一个元素结尾的最长连续递增序列的长度 和 以当前 结尾的......int beforeOneMaxLen = 1, currentMaxLen = 0;// res 赋最小值返回的最小值1int res = 1;for (int i = 1; i < nums.length; i ++) {currentMaxLen = nums[i] > nums[i - 1] ? beforeOneMaxLen + 1 : 1;beforeOneMaxLen = currentMaxLen;res = Math.max(res, currentMaxLen);}return res;}
}

贪心法：

public static int findLengthOfLCIS(int[] nums) {if (nums.length == 0) return 0;int res = 1; // 连续子序列最少也是1int count = 1;for (int i = 0; i < nums.length - 1; i++) {if (nums[i + 1] > nums[i]) { // 连续记录count++;} else { // 不连续，count从头开始count = 1;}if (count > res) res = count;}return res;
}

第三题： 718. Maximum Length of Repeated Subarray

// 版本一
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;}
}// 版本二: 滚动数组
class Solution {public int findLength(int[] nums1, int[] nums2) {int[] dp = new int[nums2.length + 1];int result = 0;for (int i = 1; i <= nums1.length; i++) {for (int j = nums2.length; j > 0; j--) {if (nums1[i - 1] == nums2[j - 1]) {dp[j] = dp[j - 1] + 1;} else {dp[j] = 0;}result = Math.max(result, dp[j]);}}return result;}
}