思想

动态规划 1 及之后的文章是实证，通过不同题目阐述 dp 思想如何应用。

实例

最长递增子序列 leetcode 300
输入：
nums: List[int]，一个整数数组；
输出：
int，最长严格递增子序列的长度。

注意区分子序列和子串：
子序列不要求连续性；
子串必须是连续的。

举例：
当 nums = [10,9,2,5,3,7,101,18] 时，最长严格递增子序列是 4 [2,3,7,101]/[2,3,7,18]

状态

这道题目有两个值，一个是当前数值，另一个是严格递增子串长度。最终要返回的是最大长度，不关心子串的元素组成，所以状态设置为当前数值的最大子串长度。

dp 数组

这里的状态是严格递增子串最大长度，dp 数组要将长度和当前数值关联起来，也就是当前数值的最大严格递增子串长度。
dp 数组长度和输入整数数组长度一致，在上例中，dp 数组是：
[1, 1, 1, 2, 2, 3, ...]

状态转移方程

整理 dp 数组的过程暗含了状态转移方程，从较小的索引向后计算最大严格递增子序列的长度，等于前序所有比当前值小的数值对应的 dp 数组值加 1 中的最大值，如果没有找到严格递增的位置，则等于 1。
沿用上例，dp[4] = dp[2] + 1
dp 数组索引 4 的当前值是 3，向前遍历找寻小于当前值 3 的位置，找到的位置是 2，对应的 dp 索引值是 1，所以 dp 索引 4 的值是 1+1=2.

初始值

任何长度为 1 的整数数组都是自身的严格递增子序列，所以 dp 数组的初始值都是 1.

编码

from typing import List


def longest_increasing_subsequence(nums: List[int]) -> int:
    # 初始化
    dp_table = [1] * len(nums)
    # 状态转移方程逐个求解，index=0 可越过
    for i in range(1, len(nums)):
        # 寻找第一个小于当前整数值的位置
        j = i - 1
        while j >= 0:
            if nums[j] < nums[i]:
                dp_table[i] = max(dp_table[i], dp_table[j] + 1)
            j -= 1
    return max(dp_table)

相关

动态规划 0
动态规划 1