1. 最长递增子序列
300. 最长递增子序列 - 力扣(LeetCode)
dp[i] 取决于 i 之前所有的dp
class Solution {public int lengthOfLIS(int[] nums) {// dp[i] 第 0 - i 位的递增子序列长度int length = nums.length;int[] dp =new int[length];Arrays.fill(dp, 1);int max = 1;for(int i = 1; i < length; i++){for(int j = 0; j < i; j++){if(nums[i] > nums[j])dp[i] = Math.max(dp[i], dp[j] + 1);}max = Math.max(dp[i], max);}return max;}
}
2. 最长连续递增序列
674. 最长连续递增序列 - 力扣(LeetCode)
dp[i] 取决于 i-1 的dp
class Solution {public int findLengthOfLCIS(int[] nums) {int length = nums.length;int[] dp = new int[length];Arrays.fill(dp, 1);int max = 1;for(int i = 1; i < length; i++){if(nums[i] > nums[i-1]){dp[i] = dp[i-1] + 1;}max = Math.max(max, dp[i]);}return max;}
}
3. 最长重复子数组
718. 最长重复子数组 - 力扣(LeetCode)
遍历两个数组,当前元素(及之前)的公共子数组 取决于 当前位置是否相等 和 前一位
注意,两个数组 中 有元素是第一个 要初始化为 1
class Solution {public int findLength(int[] nums1, int[] nums2) {//dp[i][j] nums1[i] nums2[j] 前(包含)的最长公共子数组 * 当前位置必须相等int l1 = nums1.length;int l2 = nums2.length;int[][] dp = new int[l1][l2];int max= 0;for(int i = 0; i < l1; i++){for(int j = 0; j < l2; j++){if(nums1[i] == nums2[j]){ // * 当前位置必须相等if( i == 0 || j == 0){dp[i][j] = 1;}elsedp[i][j] = dp[i-1][j-1] + 1;max = Math.max(max, dp[i][j]);}}}return max;}
}
nums1 = [1,2,3,2,1], nums2 = [3,2,1,4,7]dp[2][2] = 0 不 = 1 因为 nums1[2] != nums2[2]