[leetcode]No.300 最长上升子序列（动态规划）

最长上升子序列给定一个无序的整数数组，找到其中最长上升子序列的长度。

示例:

输入: [10,9,2,5,3,7,101,18] 输出: 4 解释: 最长的上升子序列是 [2,3,7,101]，它的长度是 4。说明:

可能会有多种最长上升子序列的组合，你只需要输出对应的长度即可。你算法的时间复杂度应该为 O(n2) 。

一直以来，自己对动态规划都不熟悉，一听到就觉得这个好难，所以面对这样的问题，思想还是停留在暴力解法，然而看了题解之后（leetcode 上面大神真多），感觉对动态规划的思路又有了一丢丢的提升，记录下分析过程，加深理解

常见的动态规划问题一般也都是按以下几个步骤去分析问题

定义状态

首先要找出我们题目求解目标是什么，比如这一题里求的是最长上升子序列的长度，那么我们就可以定义 dp[i] 代表当前数组下标之前的所有元素（含下标为 i 的元素）中最长的上升子序列，比如题目中示例 [10,9,2,5,3,7,101,18]，dp[0] 代表 [10] 的最长上升子序列长度，即 1，dp[1] 代表 [10, 9]，dp[2] 代表 [10, 9, 2]，如此类推，也就是以 nums[i] 为结尾的子数组

状态转移

定义好了状态，我们就可以找出各种状态之间的关系，如上所述，我们要求 dp[i] 这个状态的解，我们需要先知道 dp[i - 1] dp[i - 2]及之前所有状态的解，然后找出尾值小于 nums[i] 的最大 dp 值（最长子序列的长度），然后将其 + 1 即为 dp[i] 的值，若无，则为 0 + 1，考虑到题目要求的是上升子序列，[1, 2, 2, 3, 4] 这种不属于上升子序列，因为我们要把等号的情况剔除

初始/边界值

因为是把问题拆解，当问题足够小的时候，必然会有初始值，或者叫边界值，这里的边界值为 dp[0] 为 1，即其本身

输出值

这里要注意的是，dp[i] 不一定是最优解，因为这里是求最大值，计算完所有的 dp 值之后，还需要再一次遍历获取最大值

状态压缩

在常见的动态规划问题中，我们有时候会出现一些重复计算，比如斐波那契数列，我们可以把一些状态存起来，避免重复计算但是这里不可以，因为遍历到每个新的数时，要与前面每一个计算过的值来比较，所以无法压缩

代码如下：

var lengthOfLIS = function(nums) {
    const len = nums.length
    if(len < 2) return len
    // 初始化 dp 数组
    const dp = new Array(len).fill(1)
    for(let i = 1; i < len; i++) {
        for(let j = 0; j < i; j++) {
            // 找出前面小于当前值的数，将其存在 dp 中
            if(nums[j] < nums[i]) {
                dp[i] = Math.max(dp[i], dp[j] + 1)
            }
        }
    }
    let max = 1
    for(let v of dp) {
        max = v > max ? v : max
    }
    return max
}

参考题解：动态规划、优化（以贪心和二分作为子过程）

liangbus / blogging