力扣 动态规划300、最长递增子序列 354、俄罗斯套娃信封问题

回溯、双指针、链表等比较简单是因为解题逻辑比较固定
动态规划、递归之所以难，是因为只知道问题的大概的方法，具体的逻辑和实现，需要根据不同的题目做不同的思考、、

300、最长递增子序列

解题思路：

首先使用一个nums长度的数组用作记录，记录nums数组每一位作为子序列的最后一位时，这个递增的子序列的总长度，然后在上一个递增子序列的基础上去标记下一位，e.g.dp[2]之后标记dp[3]、、、
首先是去标记
nums 1 dp 1 当序列最后一位是1时，最长递增子序列长度为1
nums 1,4 dp 1,2 当序列最后一位是4时，最长递增子序列长度为2
nums 1,4,3 dp 1,2,2
nums 1,4,3,4 dp 1,2,2,3
nums 1,4,3,4,2 dp 1,2,2,3,2
nums 1,4,3,4,2,3 dp 1,2,2,3,2,3
如此这样就是 子问题，最小单位（字迹、子问题）只有一个1，然后在这个1的基础上一点点扩大这个序列，从1（nums[0]）开始得到dp[0]的数值...

代码：

class Solution {
    int lengthOfLIS(int[] nums) {
        // 定义：dp[i] 表示以 nums[i] 这个数结尾的最长递增子序列的长度
        int[] dp = new int[nums.length];
        // base case：dp 数组全都初始化为 1
        Arrays.fill(dp, 1);
        for (int i = 0; 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);
            }
        }
    
        int res = 0;
        for (int i = 0; i < dp.length; i++) {
            res = Math.max(res, dp[i]);
        }
        return res;
    }
}

354、俄罗斯套娃信封问题

这个题目就是上一道题的变形

如果明白了上一道题，这道题就很简单了
唯一的小难点就是当宽度相同时，为什么高度要降序排列
如果宽度相同，高度也升序排序，那么在调用上一道题目的函数时，就会认为是 相同宽度的信封的小高度是可以被大高度的信封给嵌套了，实际上相同宽度或者高度的信封都是不可以被嵌套的，所以是降序的

代码如下：

class Solution {
    // envelopes = [[w, h], [w, h]...]
    public int maxEnvelopes(int[][] envelopes) {
        int n = envelopes.length;
        // 按宽度升序排列，如果宽度一样，则按高度降序排列
        Arrays.sort(envelopes, new Comparator<int[]>()
        {
            public int compare(int[] a, int[] b) {
                return a[0] == b[0] ?
                        b[1] - a[1] : a[0] - b[0];
            }
        });
        // 对高度数组寻找 LIS
        int[] height = new int[n];
        for (int i = 0; i < n; i++)
            height[i] = envelopes[i][1];

        return lengthOfLIS(height);
    }

    public int lengthOfLIS(int[] nums) {
        int[] top = new int[nums.length];
        // 牌堆数初始化为 0
        int piles = 0;
        for (int i = 0; i < nums.length; i++) {
            // 要处理的扑克牌
            int poker = nums[i];

            /***** 搜索左侧边界的二分查找 *****/
            int left = 0, right = piles;
            while (left < right) {
                int mid = (left + right) / 2;
                if (top[mid] > poker) {
                    right = mid;
                } else if (top[mid] < poker) {
                    left = mid + 1;
                } else {
                    right = mid;
                }
            }
            /*********************************/
        
            // 没找到合适的牌堆，新建一堆
            if (left == piles) piles++;
            // 把这张牌放到牌堆顶
            top[left] = poker;
        }
        // 牌堆数就是 LIS 长度
        return piles;
    }

}