LeetCode 刷题笔记 - 300. 最长上升子序列

难度：

中等

描述：

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

示例:

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

来源：力扣（LeetCode）链接：leetcode-cn.com/problems/lo… 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

语言：

swift

解析：

这也是动态规划比较基础的一道题，我们依旧按照基本解题思路来分析。要求长度为 n 的序列的最长上升子序列，首先分解为子问题：

1. 求该序列长度为 0 的序列的最长上升子序列
2. 求该序列长度为 1 的序列的最长上升子序列
3. 求该序列长度为 2 的序列的最长上升子序列
4. 求该序列长度为 3 的序列的最长上升子序列
5. ...
6. 求该序列长度为 n 的序列的最长上升子序列

然后设置状态方程，我们设d(n)为该序列长度为n的时候的最长子序列长度，L[n]为序列L的第n位元素。

先来看第一个问题：
1. 求该序列长度为 0 的序列的最长上升子序列，显而易见序列长度为 0 的时候，最长子序列长度也为 0 ，所以d(0) = 0。
第二个问题：
2. 求该序列长度为 1 的序列的最长上升子序列的答案为1，所以d(1) = 1。
3. 求该序列长度为 2 的序列的最长上升子序列的情况就有所不同了，我们需要比较L[2]和L[1]的大小，如果L[2] > L[1]，则有d(2) = 2；如果L[2] < L[1]，则有d(2) = 1。
4. 求该序列长度为 3 的序列的最长上升子序列的情况会更加复杂，由于L[1]和L[2]的最长子序列是已知的，我们仅需要把L[3]分别同L[1]和L[2]比较，找到比L[3]小的。例如示例中，d(1) = 1, d(2) = 1, d(3) = 1。
5. 求该序列长度为 4 的序列的最长上升子序列，同上一个子问题一样，我们发现L[3] < L[4]，所以d(4) = 2，抽象为d(4) = d(3) + 1 = 1 + 1 = 2。
这个时候我们同时需要考虑，如果第x位元素L[x]，在[1, x)区间内有y、z两个元素小于L[x]，即L[y] < L[x]、L[z] < L[x]，那么我们需要找到d(y)和d(z)中比较大的，所以可以抽象出方程：d(x) = max{d(y), d(z)} + 1。
所以在求解：
6. 求该序列长度为 n 的序列的最长上升子序列的时候，我们可以抽象出状态转移方程：
d(i) = max{1, d(j) + 1}(j < i, L[j] < L[i])
我们需要在遍历每个元素的时候，去寻找前面元素中的最长上升子序列。

自认为表达的的还不是太好。。。可以讨论一下，我还会改进。

代码如下：

class Solution {
    func lengthOfLIS(_ nums: [Int]) -> Int {
        if nums.count == 0 {
            return 0
        }
        var dict = [Int : Int]()
        var maxLength = 1
        dict[0] = 1
        for index in 0...nums.count - 1 {
            var length = 0
            if index - 1 < 0 {
                continue
            }
            for loopIndex in 0...index - 1 {
                if nums[loopIndex] < nums[index] && (dict[loopIndex] != nil) {
                    length = max(length, dict[loopIndex]!)
                }
            }
            dict[index] = length + 1
            maxLength = max(maxLength, dict[index]!)
        }
        return maxLength
    }
}

总结

动态规划很有趣，要通过多练习才能熟悉。