动态规划-最长子序列

300. 最长递增子序列

class Solution {public int lengthOfLIS(int[] nums) {int n  = nums.length;int[] dp = new int[n];for(int i = 0; i<n; i++){dp[i] = 1;}//dp[i]表示从0-i包括i以nums[i] 结尾的最长严格递增子序列长度// dp[i] = (dp[j] + 1 , dp[i]);int result = 0;for(int i = 0; i<n;i++){for(int j = 0; j<i; j++){if(nums[i] > nums[j]){dp[i] =Math.max(dp[j]+1, dp[i]);}}result = Math.max(result,dp[i]);}return result;}
}

674. 最长连续递增序列

class Solution {public int findLengthOfLCIS(int[] nums) {//dp[i] 表示以=nums[i] 结尾的最长连续递增子序列长度；int n = nums.length;int[] dp = new int[n];for(int i = 0; i<n; i++){dp[i] = 1;}int result = 1;for(int i = 1; i<n; i++){if(nums[i] > nums[i-1]){dp[i] = dp[i-1] + 1;}result = Math.max(result,dp[i]);}return result;}
}

class Solution {public int findLength(int[] nums1, int[] nums2) {//dp[i][j] 表示 nums1从0-i和nums2从0-j的公共的长度最长的子数组的长度int m = nums1.length;int n = nums2.length;int[][] dp = new int[m+1][n+1];int result = 0;for(int i = 1; i<=m; i++){for(int j = 1; j<=n; 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;}
}