动态规划-最长递增子序列

明确 base case -> 明确「状态」-> 明确「选择」 -> 定义 dp 数组/函数的含义

最长连续递增序列（力扣674）

题目

给定一个未经排序的整数数组，找到最长且 连续递增的子序列，并返回该序列的长度。

连续递增的子序列 可以由两个下标 l 和 r（l < r）确定，如果对于每个 l <= i < r，都有 nums[i] < nums[i + 1] ，那么子序列 [nums[l], nums[l + 1], ..., nums[r - 1], nums[r]] 就是连续递增子序列。

示例 1：
1
2
3
4
>输入：nums = [1,3,5,4,7]
>输出：3
>解释：最长连续递增序列是 [1,3,5], 长度为3。
>尽管 [1,3,5,7] 也是升序的子序列, 但它不是连续的，因为 5 和 7 在原数组里被 4 隔开。 
示例 2：
1
2
3
>输入：nums = [2,2,2,2,2]
>输出：1
>解释：最长连续递增序列是 [2], 长度为1。

分析

要求最长的连续递增子序列，求最长我们尝试使用动态规划，定义dp数组为以dp[i]结尾的最长连续递增子序列。这里只需要和前一个数比较，如果比前一个数大则序列长度加1，小则跳过即可。

class Solution:
    def findLengthOfLCIS(self, nums: List[int]) -> int:
        if not nums:return 0
        dp = [1]*len(nums)
        for i in range(1,len(nums)):
            if nums[i-1]<nums[i]:
                dp[i] = max(dp[i-1]+1,dp[i])
        return max(dp)

最长递增子序列（力扣300）

题目

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

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

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

分析

首先思考这道题的暴力递归方法：

定义n = len(nums)

以nums[i]为起点，一直找到nums[n-1],中间如果i<j且nums[i]<nums[j],则[nums[i],nums[j]]是一个递增的子序列。这样可以找到以i开头的最长递增子序列。

但这样的方法在处理如[2,5,3,4]的序列时，在递归到4这个点时，[2,5]与[2,3]都是递增子序列，我们需要选择[2,3]与4组成长度为3的递增子序列。

所以，当i<j且nums[i]<nums[j]时，面临两种选择：

将nums[i]和nums[j]组成一个子序列，子序列长度+1
nums[i]放弃nums[j]，看后面还有没有更好的数字可以组合

对于递归函数来说，就可以这么实现了:

如果nums[i]>=nums[j]，放弃nums[j]，继续比较后面的元素
如果nums[i]<nums[j]，将这两个元素组成一个子序列
如果nums[i]<nums[j]，放弃nums[j]继续比较后面的元素

class Solution(object):
    def lengthOfLIS(self, nums):
        if not nums:
            return 0
        N = len(nums)
        def dfs(pre,cur):
            if cur==N:
                return 0
            a,b = 0,0
            # pre小于0是初始状态，继续往后判断
            # if条件满足说明是上升子序列，长度要+1
            if pre<0 or nums[pre]<nums[cur]:
                a = dfs(cur,cur+1)+1
            # 如果不满足可能是不满足上升子序列条件
            # 也可能是 满足条件但主动放弃
            b = dfs(pre,cur+1)
            return max(a,b)
        return dfs(-1,0)

同样，可以使用带备忘录的递归，《算法导论第三版》动态规划的章节中提到过，递归+记忆化的时间复杂度理论上和动态规划是差不多的，但实际执行中时间复杂度上还有常数级别的差异，递归调用本身就需要多耗费一点时间，这就是导致python的递归+记忆化仍然通过不了，而python的动态规划版本可以通过。

我们这里考虑动态规划的版本：

首先需要考虑dp数组的定义，我们定义为dp[i]=以i开头的最长递增子序列长度，那么dp[i+1]分三种情况：

dp[i+1]<dp[i]那么dp[i+1]=dp[i]
dp[i+1]>dp[i]那么dp[i+1]=dp[i]+1
dp[i+1]>dp[i]那么，假设j=[1,i)，if nums[j]<nums[i], dp[i+1]=dp[j]+1

注意这里dp数组需要初始化为1，因为本身算是一个递增序列

class Solution(object):
    def lengthOfLIS(self, nums):
        if not nums:
            return 0
        N = len(nums)
        dp = [1 for _ in xrange(N)]
        for i in xrange(N):
            for j in xrange(i):
                # 如果满足上升条件，更新dp数组
                if nums[j]<nums[i]:
                    dp[i] = max(dp[i],dp[j]+1)
        # 返回dp数组中的最大值
        return max(dp)