重启DAY15 线性DP 最长递增子序列

跟着灵茶山艾府大佬学习算法思路的day15（并没有在一个月内掌握hot100）

b站链接如下：

最长递增子序列【基础算法精讲 20】

dp问题常常从末尾状态往前思考比从初始状态往后思考容易，所以自顶向下的递归更容易推导出逻辑。不过爬楼梯、打家劫舍这类，状态转移只看前一步，即使不使用倒推的分解，从前往后也很直观。

最长递增子序列 题目描述：

给你一个整数数组 nums ，找到其中最长严格递增子序列的长度。

子序列 是由数组派生而来的序列，删除（或不删除）数组中的元素而不改变其余元素的顺序。例如，[3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的子序列。

示例 1：

输入：nums = [10,9,2,5,3,7,101,18]
输出：4
解释：最长递增子序列是 [2,3,7,101]，因此长度为 4 。

示例 2：

输入：nums = [0,1,0,3,2,3]
输出：4

示例 3：

输入：nums = [7,7,7,7,7,7,7]
输出：1

提示：

• 1 <= nums.length <= 2500
• -104 <= nums[i] <= 104

进阶：

• 你能将算法的时间复杂度降低到 O(n log(n)) 吗?

思路：

子序列本质是数组的一个子集，可以用子集型回溯思考。有选或不选或者枚举选哪个两个思路，如果倒着思考，假设3是子序列的最后一个数，考虑选或不选，前面的数字就需要和3比较大小，需要知道3的下标之外，还需要知道上一个数字的下标。如果用枚举选哪个，就可以直接枚举前面比3小的数字，当做子序列的倒数第二个数。

因为无法知道以哪个元素结尾的子序列会是最长的，所以最后需要遍历整个表格取最大值。LCS和编辑距离的dp维度是进度，dp[i][j] 表示处理到哪了；LIS 的 dp 维度是结尾，dp[i] 表示以 i 结尾的最优解。

	选或不选	选哪个
时间	O(n²)	O(n²)
空间	O(n²)	O(n)

如果本题不要求严格递增，那么在关键判断nums[j] < nums[i]处可以改为小于等于。

最长递增子序列和最长公共子序列是有联系的，把数组排序去重后，它的任意一个子序列必然是递增子序列。所以把它和nums计算一个最长公共子序列，就可以得到最长递增子序列了。

时间复杂度还可以进一步优化，可以换一个定义状态的视角。对于动态规划而言，如果想去优化时间复杂度，有一个进阶技巧，就是交换状态和状态值。

为什么要维护最小值呢，因为根据前面的代码，nums[j]越小越容易满足nums[j] < nums[i]，相同长度只需保留最小的nums[j]。

代码：

选或不选的思路：

var lengthOfLIS = function(nums) {
    const n = nums.length;
    const memo = new Map();

    const dfs = (i, prev) => {
        if (i === n) return 0;
        const key = i + ',' + prev;
        if (memo.has(key)) return memo.get(key);

        // 不选 nums[i]
        let res = dfs(i + 1, prev);

        // 选 nums[i]（前提：比前一个大）
        if (nums[i] > prev) {
        	res = Math.max(res, dfs(i + 1, nums[i]) + 1);
        }

        memo.set(key, res);
        return res;
    };

    return dfs(0, -Infinity);
};

选哪个的思路（时间和空间更优）：

var lengthOfLIS = function(nums) {
    const n = nums.length;
    const memo = new Array(n).fill(-1);

    const dfs = (i) => {
        if (memo[i] !== -1) return memo[i];
        let res = 0;
        for (let j = 0; j < i; j++) {
            if (nums[j] < nums[i]) {
                // 当到达i时，尝试构造以i为结尾的子序列
                // 遍历所有位置小于i的子序列，找出最大的递增子序列长度
                res = Math.max(res, dfs(j));
            }
        }
        memo[i] = res + 1; // 将i拼接到子序列后
        return memo[i];
    };

    let ans = 0;
    for (let i = 0; i < n; i++) {
        ans = Math.max(ans, dfs(i));
    }
    return ans;
};

递推：

var lengthOfLIS = function(nums) {
    const n = nums.length;
    const dp = new Array(n).fill(0);

    for (let i = 0; i < n; i++) { // 遍历不用考虑返回值，直接修改，删掉所有return
        let res = 0;
        for (let j = 0; j < i; j++) {
            if (nums[j] < nums[i]) {
                // 当到达i时，尝试构造以i为结尾的子序列
                // 遍历所有位置小于i的子序列，找出最大的递增子序列长度
                res = Math.max(res, dp[j]);
            }
        }
        dp[i] = res + 1; // 将i拼接到子序列后
    };

    let ans = 0;
    for (let i = 0; i < n; i++) {
        ans = Math.max(ans, dp[i]);
    }
    return ans;
};

究极方案，贪心 + 二分查找：

var lengthOfLIS = function(nums) {
    const g = []; // g[len] = 长度为len的递增子序列的最小结尾值

    for (const x of nums) {
        // 在g中找第一个 >= x 的位置（左边界）
        let lo = 0, hi = g.length;
        while (lo < hi) {
            const mid = (lo + hi) >> 1;
            if (g[mid] < x) lo = mid + 1;
            else hi = mid;
        }

        if (lo === g.length) {
            g.push(x); // x比所有结尾都大，可以接上，长度+1
        } else {
            g[lo] = x; // 更新长度为lo+1的最小结尾值
        }
    }

    return g.length;
};

总结：

这个贪心+二分有点难了，貌似一般面试掌握到o(n*2)的就行了，不过还是尽量理解掌握吧。