01. 线性 DP 知识（一）

1. 线性动态规划简介

线性动态规划：具有「线性」阶段划分的动态规划方法统称为线性动态规划（简称为「线性 DP」），如下图所示。

如果状态包含多个维度，但是每个维度上都是线性划分的阶段，也属于线性 DP。比如背包问题、区间 DP、数位 DP 等都属于线性 DP。

线性 DP 问题的划分方法有多种方式。

如果按照「状态的维度数」进行分类，我们可以将线性 DP 问题分为：一维线性 DP 问题、二维线性 DP 问题，以及多维线性 DP 问题。
如果按照「问题的输入格式」进行分类，我们可以将线性 DP 问题分为：单串线性 DP 问题、双串线性 DP 问题、矩阵线性 DP 问题，以及无串线性 DP 问题。

本文中，我们将按照问题的输入格式进行分类，对线性 DP 问题中各种类型问题进行一一讲解。

2. 单串线性 DP 问题

单串线性 DP 问题：问题的输入为单个数组或单个字符串的线性 DP 问题。状态一般可定义为 $d p [i]$ ，表示为：
「以数组中第 $i$ 个位置元素 $n u m s [i]$ 为结尾的子数组（ $n u m s [0] . . . n u m s [i]$ ）」的相关解。
「以数组中第 $i - 1$ 个位置元素 $n u m s [i - 1]$ 为结尾的子数组（ $n u m s [0] . . . n u m s [i - 1]$ ）」的相关解。
「以数组中前 $i$ 个元素为子数组（ $n u m s [0] . . . n u m s [i - 1]$ ）」的相关解。

这 $3$ 种状态的定义区别在于相差一个元素 $n u m s [i]$ 。

第 $1$ 种状态：子数组的长度为 $i + 1$ ，子数组长度不可为空；
第 $2$ 种状态、第 $3$ 种状态：这两种状态描述是相同的。子数组的长度为 $i$ ，子数组长度可为空。在 $i = 0$ 时，方便用于表示空数组（以数组中前 $0$ 个元素为子数组）。

2.1 最长递增子序列

单串线性 DP 问题中最经典的问题就是「最长递增子序列（Longest Increasing Subsequence，简称 LIS）」。

2.1.2 题目大意

描述：给定一个整数数组 $n u m s$ 。

要求：找到其中最长严格递增子序列的长度。

说明：

子序列：由数组派生而来的序列，删除（或不删除）数组中的元素而不改变其余元素的顺序。例如， $[3, 6, 2, 7]$ 是数组 $[0, 3, 1, 6, 2, 2, 7]$ 的子序列。
$1 \leq n u m s . l e n g t h \leq 2500$ 。
$- 10^{4} \leq n u m s [i] \leq 10^{4}$ 。

示例：

示例 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

2.1.3 解题思路

思路 1：动态规划

2. 定义状态

定义状态 $d p [i]$ 表示为：以 $n u m s [i]$ 结尾的最长递增子序列长度。

3. 状态转移方程

一个较小的数后边如果出现一个较大的数，则会形成一个更长的递增子序列。

对于满足 $0 \leq j < i$ 的数组元素 $n u m s [j]$ 和 $n u m s [i]$ 来说：

如果 $n u m s [j] < n u m s [i]$ ，则 $n u m s [i]$ 可以接在 $n u m s [j]$ 后面，此时以 $n u m s [i]$ 结尾的最长递增子序列长度会在「以 $n u m s [j]$ 结尾的最长递增子序列长度」的基础上加 $1$ ，即： $d p [i] = d p [j] + 1$ 。
如果 $n u m s [j] \geq n u m s [i]$ ，则 $n u m s [i]$ 不可以接在 $n u m s [j]$ 后面，可以直接跳过。

综上，我们的状态转移方程为： $d p [i] = m a x (d p [i], d p [j] + 1), 0 \leq j < i, n u m s [j] < n u m s [i]$ 。

4. 初始条件

默认状态下，把数组中的每个元素都作为长度为 $1$ 的递增子序列。即 $d p [i] = 1$ 。

5. 最终结果

根据我们之前定义的状态， $d p [i]$ 表示为：以 $n u m s [i]$ 结尾的最长递增子序列长度。那为了计算出最大的最长递增子序列长度，则需要再遍历一遍 $d p$ 数组，求出最大值即为最终结果。

思路 1：动态规划代码

class Solution:
    def lengthOfLIS(self, nums: List[int]) -> int:
        size = len(nums)
        dp = [1 for _ in range(size)]

        for i in range(size):
            for j in range(i):
                if nums[i] > nums[j]:
                    dp[i] = max(dp[i], dp[j] + 1)
        
        return max(dp)

思路 1：复杂度分析

时间复杂度： $O (n^{2})$ 。两重循环遍历的时间复杂度是 $O (n^{2})$ ，最后求最大值的时间复杂度是 $O (n)$ ，所以总体时间复杂度为 $O (n^{2})$ 。
空间复杂度： $O (n)$ 。用到了一维数组保存状态，所以总体空间复杂度为 $O (n)$ 。

2.2 最大子数组和

单串线性 DP 问题中除了子序列相关的线性 DP 问题，还有子数组相关的线性 DP 问题。

注意：
子序列：由数组派生而来的序列，删除（或不删除）数组中的元素而不改变其余元素的顺序。
子数组：指的是数组中的一个连续子序列。
「子序列」与「子数组」都可以看做是原数组的一部分，而且都不会改变原来数组中元素的相对顺序。其区别在于数组元素是否要求连续。

2.2.2 题目大意

描述：给定一个整数数组 $n u m s$ 。

要求：找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。

说明：

子数组：指的是数组中的一个连续部分。
$1 \leq n u m s . l e n g t h \leq 10^{5}$ 。
$- 10^{4} \leq n u m s [i] \leq 10^{4}$ 。

示例：

示例 1：

输入：nums = [-2,1,-3,4,-1,2,1,-5,4]
输出：6
解释：连续子数组 [4,-1,2,1] 的和最大，为 6。

示例 2：

输入：nums = [1]
输出：1

2.2.3 解题思路

思路 1：动态规划

3. 状态转移方程

状态 $d p [i]$ 为：以第 $i$ 个数结尾的连续子数组的最大和。则我们可以从「第 $i - 1$ 个数结尾的连续子数组的最大和」，以及「第 $i$ 个数的值」来讨论 $d p [i]$ 。

如果 $d p [i - 1] < 0$ ，则「第 $i - 1$ 个数结尾的连续子数组的最大和」+「第 $i$ 个数的值」<「第 $i$ 个数的值」，即： $d p [i - 1] + n u m s [i] < n u m s [i]$ 。所以，此时 $d p [i]$ 应取「第 $i$ 个数的值」，即 $d p [i] = n u m s [i]$ 。
如果 $d p [i - 1] \geq 0$ ，则「第 $i - 1$ 个数结尾的连续子数组的最大和」 +「第 $i$ 个数的值」 >= 第 $i$ 个数的值，即： $d p [i - 1] + n u m s [i] \geq n u m s [i]$ 。所以，此时 $d p [i]$ 应取「第 $i - 1$ 个数结尾的连续子数组的最大和」+「第 $i$ 个数的值」，即 $d p [i] = d p [i - 1] + n u m s [i]$ 。

归纳一下，状态转移方程为：

$d p [i] = {\begin{cases} n u m s [i], & d p [i - 1] < 0 \\ d p [i - 1] + n u m s [i] & d p [i - 1] \geq 0 \end{cases}$

4. 初始条件

第 $0$ 个数结尾的连续子数组的最大和为 $n u m s [0]$ ，即 $d p [0] = n u m s [0]$ 。

5. 最终结果

根据状态定义， $d p [i]$ 为：以第 $i$ 个数结尾的连续子数组的最大和。则最终结果应为所有 $d p [i]$ 的最大值，即 $m a x (d p)$ 。

思路 1：代码

class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        size = len(nums)
        dp = [0 for _ in range(size)]

        dp[0] = nums[0]
        for i in range(1, size):
            if dp[i - 1] < 0:
                dp[i] = nums[i]
            else:
                dp[i] = dp[i - 1] + nums[i]
        return max(dp)

思路 1：复杂度分析

时间复杂度： $O (n)$ ，其中 $n$ 为数组 $n u m s$ 的元素个数。
空间复杂度： $O (n)$ 。

思路 2：动态规划 + 滚动优化

因为 $d p [i]$ 只和 $d p [i - 1]$ 和当前元素 $n u m s [i]$ 相关，我们也可以使用一个变量 $s u b M a x$ 来表示以第 $i$ 个数结尾的连续子数组的最大和。然后使用 $a n s M a x$ 来保存全局中最大值。

思路 2：代码

class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        size = len(nums)
        subMax = nums[0]
        ansMax = nums[0]

        for i in range(1, size):
            if subMax < 0:
                subMax = nums[i]
            else:
                subMax += nums[i]
            ansMax = max(ansMax, subMax)
        return ansMax

思路 2：复杂度分析

时间复杂度： $O (n)$ ，其中 $n$ 为数组 $n u m s$ 的元素个数。
空间复杂度： $O (1)$ 。

2.3 最长的斐波那契子序列的长度

有一些单串线性 DP 问题在定义状态时需要考虑两个结束位置，只考虑一个结束位置的无法清楚描述问题。这时候我们就需要需要增加一个结束位置维度来定义状态。

2.3.2 题目大意

描述：给定一个严格递增的正整数数组 $a r r$ 。

要求：从数组 $a r r$ 中找出最长的斐波那契式的子序列的长度。如果不存斐波那契式的子序列，则返回 0。

说明：

斐波那契式序列：如果序列 $X_{1}, X_{2}, . . ., X_{n}$ 满足：
- $n \geq 3$ ；
- 对于所有 $i + 2 \leq n$ ，都有 $X_{i} + X_{i + 1} = X_{i + 2}$ 。
则称该序列为斐波那契式序列。
斐波那契式子序列：从序列 $A$ 中挑选若干元素组成子序列，并且子序列满足斐波那契式序列，则称该序列为斐波那契式子序列。例如： $A = [3, 4, 5, 6, 7, 8]$ 。则 $[3, 5, 8]$ 是 $A$ 的一个斐波那契式子序列。
$3 \leq a r r . l e n g t h \leq 1000$ 。
$1 \leq a r r [i] < a r r [i + 1] \leq 10^{9}$ 。

示例：

示例 1：

输入: arr = [1,2,3,4,5,6,7,8]
输出: 5
解释: 最长的斐波那契式子序列为 [1,2,3,5,8]。

示例 2：

输入: arr = [1,3,7,11,12,14,18]
输出: 3
解释: 最长的斐波那契式子序列有 [1,11,12]、[3,11,14] 以及 [7,11,18]。

2.3.3 解题思路

思路 1：暴力枚举（超时）

假设 $a r r [i]$ 、 $a r r [j]$ 、 $a r r [k]$ 是序列 $a r r$ 中的 $3$ 个元素，且满足关系： $a r r [i] + a r r [j] == a r r [k]$ ，则 $a r r [i]$ 、 $a r r [j]$ 、 $a r r [k]$ 就构成了 $a r r$ 的一个斐波那契式子序列。

通过 $a r r [i]$ 、 $a r r [j]$ ，我们可以确定下一个斐波那契式子序列元素的值为 $a r r [i] + a r r [j]$ 。

因为给定的数组是严格递增的，所以对于一个斐波那契式子序列，如果确定了 $a r r [i]$ 、 $a r r [j]$ ，则可以顺着 $a r r$ 序列，从第 $j + 1$ 的元素开始，查找值为 $a r r [i] + a r r [j]$ 的元素。找到 $a r r [i] + a r r [j]$ 之后，然后再顺着查找子序列的下一个元素。

简单来说，就是确定了 $a r r [i]$ 、 $a r r [j]$ ，就能尽可能的得到一个长的斐波那契式子序列，此时我们记录下子序列长度。然后对于不同的 $a r r [i]$ 、 $a r r [j]$ ，统计不同的斐波那契式子序列的长度。

最后将这些长度进行比较，其中最长的长度就是答案。

思路 1：代码

class Solution:
    def lenLongestFibSubseq(self, arr: List[int]) -> int:
        size = len(arr)
        ans = 0
        for i in range(size):
            for j in range(i + 1, size):
                temp_ans = 0
                temp_i = i
                temp_j = j
                k = j + 1
                while k < size:
                    if arr[temp_i] + arr[temp_j] == arr[k]:
                        temp_ans += 1
                        temp_i = temp_j
                        temp_j = k
                    k += 1
                if temp_ans > ans:
                    ans = temp_ans

        if ans > 0:
            return ans + 2
        else:
            return ans

思路 1：复杂度分析

时间复杂度： $O (n^{3})$ ，其中 $n$ 为数组 $a r r$ 的元素个数。
空间复杂度： $O (1)$ 。

对于 $a r r [i]$ 、 $a r r [j]$ ，要查找的元素 $a r r [i] + a r r [j]$ 是否在 $a r r$ 中，我们可以预先建立一个反向的哈希表。键值对关系为 $v a l u e : i d x$ ，这样就能在 $O (1)$ 的时间复杂度通过 $a r r [i] + a r r [j]$ 的值查找到对应的 $a r r [k]$ ，而不用像原先一样线性查找 $a r r [k]$ 了。

思路 2：代码

class Solution:
    def lenLongestFibSubseq(self, arr: List[int]) -> int:
        size = len(arr)
        ans = 0
        idx_map = dict()
        for idx, value in enumerate(arr):
            idx_map[value] = idx
        
        for i in range(size):
            for j in range(i + 1, size):
                temp_ans = 0
                temp_i = i
                temp_j = j
                while arr[temp_i] + arr[temp_j] in idx_map:
                    temp_ans += 1
                    k = idx_map[arr[temp_i] + arr[temp_j]]
                    temp_i = temp_j
                    temp_j = k

                if temp_ans > ans:
                    ans = temp_ans

        if ans > 0:
            return ans + 2
        else:
            return ans

思路 2：复杂度分析

时间复杂度： $O (n^{2})$ ，其中 $n$ 为数组 $a r r$ 的元素个数。
空间复杂度： $O (n)$ 。

思路 3：动态规划 + 哈希表

1. 划分阶段

按照斐波那契式子序列相邻两项的结尾位置进行阶段划分。

2. 定义状态

定义状态 $d p [i] [j]$ 表示为：以 $a r r [i]$ 、 $a r r [j]$ 为结尾的斐波那契式子序列的最大长度。

3. 状态转移方程

以 $a r r [j]$ 、 $a r r [k]$ 结尾的斐波那契式子序列的最大长度 = 满足 $a r r [i] + a r r [j] = a r r [k]$ 条件下，以 $a r r [i]$ 、 $a r r [j]$ 结尾的斐波那契式子序列的最大长度加 $1$ 。即状态转移方程为： $d p [j] [k] = m a x_{(A [i] + A [j] = A [k], i < j < k)} (d p [i] [j] + 1)$ 。

4. 初始条件

默认状态下，数组中任意相邻两项元素都可以作为长度为 $2$ 的斐波那契式子序列，即 $d p [i] [j] = 2$ 。

5. 最终结果

根据我们之前定义的状态， $d p [i] [j]$ 表示为：以 $a r r [i]$ 、 $a r r [j]$ 为结尾的斐波那契式子序列的最大长度。那为了计算出最大的最长递增子序列长度，则需要在进行状态转移时，求出最大值 $a n s$ 即为最终结果。

因为题目定义中，斐波那契式中 $n \geq 3$ ，所以只有当 $a n s \geq 3$ 时，返回 $a n s$ 。如果 $a n s < 3$ ，则返回 $0$ 。

注意：在进行状态转移的同时，我们应和「思路 2：哈希表」一样采用哈希表优化的方式来提高效率，降低算法的时间复杂度。

思路 3：代码

class Solution:
    def lenLongestFibSubseq(self, arr: List[int]) -> int:
        size = len(arr)
        
        dp = [[0 for _ in range(size)] for _ in range(size)]
        ans = 0

        # 初始化 dp
        for i in range(size):
            for j in range(i + 1, size):
                dp[i][j] = 2

        idx_map = {}
        # 将 value : idx 映射为哈希表，这样可以快速通过 value 获取到 idx
        for idx, value in enumerate(arr):
            idx_map[value] = idx

        for i in range(size):
            for j in range(i + 1, size):
                if arr[i] + arr[j] in idx_map:    
                    # 获取 arr[i] + arr[j] 的 idx，即斐波那契式子序列下一项元素
                    k = idx_map[arr[i] + arr[j]]
                    
                    dp[j][k] = max(dp[j][k], dp[i][j] + 1)
                    ans = max(ans, dp[j][k])

        if ans >= 3:
            return ans
        return 0

思路 3：复杂度分析

时间复杂度： $O (n^{2})$ ，其中 $n$ 为数组 $a r r$ 的元素个数。
空间复杂度： $O (n)$ 。

3. 双串线性 DP 问题

双串线性 DP 问题：问题的输入为两个数组或两个字符串的线性 DP 问题。状态一般可定义为 $d p [i] [j]$ ，表示为：
「以第一个数组中第 $i$ 个位置元素 $n u m s 1 [i]$ 为结尾的子数组（ $n u m s 1 [0] . . . n u m s 1 [i]$ ）」与「以第二个数组中第 $j$ 个位置元素 $n u m s 2 [j]$ 为结尾的子数组（ $n u m s 2 [0] . . . n u m s 2 [j]$ ）」的相关解。
「以第一个数组中第 $i - 1$ 个位置元素 $n u m s 1 [i - 1]$ 为结尾的子数组（ $n u m s 1 [0] . . . n u m s 1 [i - 1]$ ）」与「以第二个数组中第 $j - 1$ 个位置元素 $n u m s 2 [j - 1]$ 为结尾的子数组（ $n u m s 2 [0] . . . n u m s 2 [j - 1]$ ）」的相关解。
「以第一个数组中前 $i$ 个元素为子数组（ $n u m s 1 [0] . . . n u m s 1 [i - 1]$ ）」与「以第二个数组中前 $j$ 个元素为子数组（ $n u m s 2 [0] . . . n u m s 2 [j - 1]$ ）」的相关解。

这 $3$ 种状态的定义区别在于相差一个元素 $n u m s 1 [i]$ 或 $n u m s 2 [j]$ 。

第 $1$ 种状态：子数组的长度为 $i + 1$ 或 $j + 1$ ，子数组长度不可为空
第 $2$ 种状态、第 $3$ 种状态：子数组的长度为 $i$ 或 $j$ ，子数组长度可为空。 $i = 0$ 或 $j = 0$ 时，方便用于表示空数组（以数组中前 $0$ 个元素为子数组）。

3.1 最长公共子序列

双串线性 DP 问题中最经典的问题就是「最长公共子序列（Longest Common Subsequence，简称 LCS）」。

3.1.1 题目链接

1143. 最长公共子序列 - 力扣

3.1.2 题目大意

描述：给定两个字符串 $t e x t 1$ 和 $t e x t 2$ 。

要求：返回两个字符串的最长公共子序列的长度。如果不存在公共子序列，则返回 $0$ 。

说明：

子序列：原字符串在不改变字符的相对顺序的情况下删除某些字符（也可以不删除任何字符）后组成的新字符串。
公共子序列：两个字符串所共同拥有的子序列。
$1 \leq t e x t 1. l e n g t h, t e x t 2. l e n g t h \leq 1000$ 。
$t e x t 1$ 和 $t e x t 2$ 仅由小写英文字符组成。

示例：

示例 1：

输入：text1 = "abcde", text2 = "ace" 
输出：3  
解释：最长公共子序列是 "ace"，它的长度为 3。

示例 2：

输入：text1 = "abc", text2 = "abc"
输出：3
解释：最长公共子序列是 "abc"，它的长度为 3。