力扣labuladong一刷day60天动态规划

力扣labuladong一刷day60天动态规划

一、300. 最长递增子序列

题目链接：https://leetcode.cn/problems/longest-increasing-subsequence/description/
思路：定义dp数组，dp[i]表示在[0,i]区间以nums[i]为结尾时的最长子序列的长度。子序列的起始位置可以是任意一个位置，故dp数组全部初始化为1。求dp[i]需要考虑区间[0,i-1]内的每一个元素是否加入，进行考虑还有一个先决条件，即nums[j]<nums[i]，0<=j<i，因为求dp[i]是以nums[i]为结尾的，要加入的元素必须得小于nums[i]，然后才是考虑是否把nums[j]加入，加入的话为dp[j]+1,不加入的话为历史记录的最大值d[i]，递推公式为dp[i]=max(dp[i], dp[j]+1)。

class Solution {
     public int lengthOfLIS(int[] nums) {
        int[] dp = new int[nums.length];
        Arrays.fill(dp, 1);
        int max = 1;
        for (int i = 1; i < nums.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;
    }
}

二、354. 俄罗斯套娃信封问题

题目链接：https://leetcode.cn/problems/russian-doll-envelopes/description/
思路：和上题类似，不过需要先排序一下，降二维为一维，[[5,4],[6,4],[6,7],[2,3]]，a[i][0]先升序，若相等a[i][1]降序，之后就降低为一维了和上一题的处理步骤一样了，但是动态规划的时间复杂度是n2，超时了。

class Solution {
     public int maxEnvelopes(int[][] envelopes) {
        Arrays.sort(envelopes, (e1, e2) -> {
            return e1[0] == e2[0] ? e2[1] - e1[1] : e1[0] - e2[0];
        });

        int[] dp = new int[envelopes.length];
        Arrays.fill(dp, 1);
        int max = 1;
        for (int i = 1; i < envelopes.length; i++) {
            for (int j = 0; j < i; j++) {
                if (envelopes[j][1] < envelopes[i][1]) {
                    dp[i] = Math.max(dp[i], dp[j]+1);
                }
            }
            max = Math.max(dp[i], max);
        }
        return max;
    }
}

采用二分查找的方法可以把时间复杂度降低到nlogn。

class Solution {
     public int maxEnvelopes(int[][] envelopes) {
        Arrays.sort(envelopes, (e1, e2)->{
            return e1[0] == e2[0] ? e2[1]-e1[1] : e1[0]-e2[0];
        });
        List<Integer> list = new ArrayList<>();
        list.add(envelopes[0][1]);
        for (int i = 1; i < envelopes.length; i++) {
            int temp = envelopes[i][1];
            if (temp > list.get(list.size()-1)) {
                list.add(temp);
            }else {
                list.set(bs(list, temp), temp);
            }
        }
        return list.size();
    }
    int bs(List<Integer> nums, int target) {
        int left = 0, right = nums.size()-1;
        while (left < right) {
            int mid = left + (right-left)/2;
            if (nums.get(mid) < target) {
                left = mid + 1;
            }else {
                right = mid;
            }
        }
        return left;
    }
}