动态规划（二）最长递增子序列

最长递增子序列

给你一个整数数组 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)) 吗?

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/longest-increasing-subsequence

tips:

动态规划题目的核心就是找出大规模与小规模之间的关系。

拿示例1来说，A = [10, 9, 2, 5, 3, 7, 101, 18]

比 A 规模更小的是B = [10, 9, 2, 5, 3, 7, 101] ，若知道 B 中的最长递增子序列的长度 4 后能否在此基础上快速推断出A的最长子序列？显然不能。因为我们不知道 A比 B 多出的尾部元素 18是否可以加到某个现有最长子序列的尾部，形成更长的子序列。

不管是自顶向下的函数递归法，还是自底向上的数组法（也叫dp数组法，动态规划 dynamic programming，简称dp），我们最最开始应该做的就是明确 函数（返回值）含义 或 dp数组中下标i与值dp[i]的含义。

我们通常可以在定义中添加一些限制条件，便于我们找出不同规模之间的递推关系（动态转移方程）。

对比这两种定义：

是否添加限制	定义
否	dp[i]：数组nums[0:i+1] （python切片前闭后开）中最长递增子序列的长度
是	dp[i]：数组nums[0:i+1] 中以nums[i] 这个数结尾的最长递增子序列的长度

尝试寻找递推关系

nums = [10, 9, 2, 5, 3, 7, 101, 18]

不加限制：

dp[0]	dp[1]	dp[2]	dp[3]	dp[4]	dp[5]	dp[6]	dp[7]
1	1	1	2	2	3	4	4

这个过程中，dp[大] 的计算不能依赖已知的dp[小]。不能依赖即不能递推，所以这是糟糕的定义🥴

添加限制：

dp[i]	nums[i]	nums[0:i+1]	以nums[i]结尾最长递增子序列	长度
dp[0]	10	[10]	[10]	1
dp[1]	9	[10, 9]	[9]	1
dp[2]	2	[10, 9, 2]	[2]	1
dp[3]	5	[10, 9, 2, 5]	[2, 5]	2

能否利用dp[小] 推断 dp[大] ❓

若nums[i] 比 nums[x] 大，nums[i] 就可以加到以nums[x]为结尾的最长递增序列后面。以nums[i]结尾的递增子序列长度比以nums[x]结尾的递增子序列长1

if nums[i] > nums[比i小]：
	dp[i] = dp[比i小] + 1

dp[i]	nums[i]	nums[0:i+1]	以nums[i]结尾最长递增子序列	长度
dp[4]	3 > nums[2]	[10, 9, 2, 5, 3 ]	[2] + [3] = [2, 3]	dp[2]+1=2

nums[4] = 3 ，比 nums[2] = 2 大。所以3可以加到以2为结尾的递增序列 [2] 中，形成新的递增子序列 [2, 3]。 dp[4] = dp[2] + 1 = 2

dp[i]	nums[i]	nums[0:i+1]	以nums[i]结尾最长递增子序列	长度
dp[5]	7 > nums[4]	[10, 9, 2, 5, 3, 7]	[2, 3] + [7] = [2, 3, 7]	dp[4] + 1= 3
	7 > nums[3]		[2, 5] +[7] = [2, 5, 7]	dp[3] + 1= 3
	7 > num[2]		[2] + [7] = [2, 7]	dp[2] + 1 = 2
				max(3, 3, 2) = 3

若nums[i] 大于多个nums[比i小]，dp[i] = max(dp[比i小]+1，dp[比i小]+1)

差不多可以可代码了。

代码

自底向上 dp数组法

nums = [10, 9, 2, 5, 3, 7, 101, 18]
# dp数组
# 定义dp数组下标含义
# dp[i], 以nums[i]这个数结尾的最长递增子序列的长度
# 定义决定了数组大小
# base case
dp = [1] * (len(nums))

# dp[大] 依赖dp[小] 先计算di[小]
for i in range(1, len(nums)):
    for j in range(0, i):
        if nums[i] > nums[j]:
            dp[i] = max(dp[i], dp[j] + 1)

自顶向下 函数递归法

# 最长递增子序列
nums = [10, 9, 2, 5, 3, 7, 101, 18]

# 自顶向下添加备忘录
# base case 已在备忘录中
memo = {0: 1}
def func(n):
    # func(i) 代表以nums[i]这个数结尾的最长递增子序列的长度
    # func(2) 代表以nums[2]这个数结尾的最长递增子序列(2)的长度
    # func(4) 代表以nums[4]这个数结尾的最长递增子序列(2,3)的长度
    if n in memo.keys():
        return memo[n]
    # 查看调用次数,验证备忘录功效
    print("函数调用func(", n, ")")
    max_length = 1
    for i in range(n - 1, -1, -1):
        val = func(i)
        if nums[n] > nums[i]:
            max_length = max(max_length, val + 1)
    memo[n] = max_length
    return max_length

无备忘录，用于对比的绿叶

# 最长递增子序列
nums = [10, 9, 2, 5, 3, 7, 101, 18]
# 自定向下解法
def func(n):
    # func(i) 代表以nums[i]这个数结尾的最长递增子序列的长度
    # func(2) 代表以nums[2]这个数结尾的最长递增子序列(2)的长度
    # func(4) 代表以nums[4]这个数结尾的最长递增子序列(2,3)的长度
    # 查看调用次数
    print("函数调用func(", n, ")")
    if n == 0:
        return 1
    max_length = 1
    for i in range(n - 1, -1, -1):
        val = func(i)
        if nums[n] > nums[i]:
            max_length = max(max_length, val + 1)
    return max_length