Day 33 动态规划 Part10

300. 最长递增子序列

动态规划的版本是挺好理解的，dp[i]代表了以第i个数字结尾的最长递增子序列的长度，dp[0]显然为1。dp如何更新呢？ i > 0: dp[i] = 在i之前，最大的小于nums[i]的数nums[j] dp[i] = dp[j] + 1，所以就是需要找到比nums[i]小的最大的数，遍历就可以得到。

class Solution {
    public int lengthOfLIS(int[] nums) {
        int[] dp = new int[nums.length];
        Arrays.fill(dp, 1);
        for(int i = 1; i < nums.length; i++)
            for(int j = 0; j < i; j++)  //找到比nums[i]小的
                if(nums[i] > nums[j]) dp[i] = Math.max(dp[i], dp[j] + 1);
        int max = 0;
        for(int num : dp) max = Math.max(num, max);
        return max;
    }
}

这个题解我也真是不想写了，心里好乱。看别人的题解吧，写的很清楚。

class Solution {
    public int lengthOfLIS(int[] nums) {
        int[] l = new int[nums.length + 1];  
        // l[i]代表可以形成长度为i的递增序列的末尾的最小值
        // 例如[2, 5, 3]可以形成长度为2的序列中[2, 3], [2, 5]末尾可以选3，或5，最小值为3，此时l[2] = 3
        int len = 1;
        l[1] = nums[0]; // l并非一开始就确定下来，而是不断的更新，代表了已经遍历的数组中的满足上述定义的l数组
        for(int i = 1; i < nums.length; i++){
            if(nums[i] > l[len]) l[++len] = nums[i];  // 当遇到大于序列末尾最大值时，说明序列还能更长，更新l数组和len
            else{
                l[binarySearch(l, 1, len, nums[i])] = nums[i];  // 找到l数组中，第一个大于当前
            } 
        }
        return len;
    }
    public int binarySearch(int[] l, int left, int right, int val){ // 左闭右闭，找到第一个大于val的位置
        while(left <= right){
            int mid = (left + right) / 2;
            if(l[mid] == val) return mid;
            if(l[mid] > val) right = mid - 1;
            else left = mid + 1;
        }
        return left;
    }
}

674. 最长连续递增序列

class Solution {
    public int findLengthOfLCIS(int[] nums) {
        int max = 1, len = 1;
        for(int i = 1; i < nums.length; i++){
            if(nums[i] > nums[i-1]) max = Math.max(max, ++len);
            else len = 1;
        }
        return max;
    }
}

718. 最长重复子数组

我都不知道我为什么要死磕那个滑动窗口的版本，虽然硬调出来了，但这要一次写出来不犯错对我来说有点不可能。动态规划这个多好啊，清清楚楚，不容易犯错。下次别这样了。

class Solution {
    public int findLength(int[] nums1, int[] nums2) {
        int ans = 0;
        int n1 = nums1.length, n2 = nums2.length;
        int[][] dp = new int[n1+1][n2+1];
        for(int i = n1 - 1; i >= 0; i--){
            for(int j = n2 - 1; j >= 0; j--){
                dp[i][j] = nums1[i] == nums2[j] ? dp[i+1][j+1] + 1 : 0;
                ans = Math.max(ans, dp[i][j]);
            }
        }
        return ans;
    }
}