# DP 专题

分段决策的最优解问题很容易想到递归解法，如果画出决策树后发现大量重复节点，那么就可以考虑使用 DP。

# 解题方法

解法一：

定义「状态空间」
定义「状态转移方程」
初始化「base case」

解法一很难用，因为第一步的状态空间就很难定义。解法二：

在脑海中采用暴力递归解法，画出决策树
简化决策树中的节点数量

# 状态空间

标准的状态空间一般是一维数组、二维数组、三维数组，但也可能是其它结构。

一般需要冗余空间表示「base case」。以二维数组为例，我们用第一行和第一列来存放 base case。

x x x x x x
x o o o o o
x o o o o o
x o o o o o

不同题的状态空间定义不一样，这就需要有大量的刷题经验，有时还要一些灵感。所以只能靠大家多练，这里没有太多东西可以介绍。

# base case 初始化

可以在循环外初始化 base case，也可以在循环内初始化 base case。

以1143. 最长公共子序列 (opens new window)为例，介绍两种填写初始状态的方法。

1143 循环外填写初始状态

class Solution:
    def longestCommonSubsequence(self, a: str, b: str) -> int:
        if not a or not b: return 0
        n, m = len(a), len(b)
        dp = [[None]*(m+1) for _ in range(n+1)]
        for i in range(0, n+1): dp[i][0] = 0
        for j in range(0, m+1): dp[0][j] = 0
        for i in range(1, n+1):
            for j in range(1, m+1):
                if a[i-1] == b[j-1]: dp[i][j] = dp[i-1][j-1] + 1
                else: dp[i][j] = max(dp[i][j-1], dp[i-1][j])
        return dp[n][m]

1143 循环内填写初始状态

class Solution:
    def longestCommonSubsequence(self, a: str, b: str) -> int:
        if not a or not b: return 0
        n, m = len(a), len(b)
        dp = [[None]*(m+1) for _ in range(n+1)]
        for i in range(0, n + 1):
            for j in range(0, m + 1):
                if i == 0 or j == 0: dp[i][j] = 0
                elif a[i-1] == b[j-1]: dp[i][j] = dp[i-1][j-1] + 1
                else: dp[i][j] = max(dp[i][j-1], dp[i-1][j])
        return dp[n][m]

# 状态转移方程

这其实很像数学归纳法。这里总结了多种形式的状态转移方程：

DP[i - 1] -> DP[i] 根据上一个状态推导当前状态
DP[i - 1], DP[i - 2] -> DP[i] 根据上两个状态推导当前状态
DP[0...i - 1] -> DP[i] 根据历史状态推导当前状态
DP[i] -> DP[i...N] 根据当前状态推导未来状态

322. 零钱兑换 (opens new window)可以根据历史推当前，也可以根据当前推未来。

322 根据历史推当前

class Solution:
    def coinChange(self, coins: List[int], amount: int) -> int:
        n = amount
        dp = [math.inf]*(n+1)
        dp[0] = 0
        for i in range(1, n+1):
            for coin in coins:
                if i - coin >= 0:
                    dp[i] = min(dp[i], dp[i-coin] + 1)
        return dp[n] if dp[n] != math.inf else -1

322 根据当前推未来

class Solution:
    def coinChange(self, coins: List[int], amount: int) -> int:
        n = amount
        dp = [math.inf]*(n+1)
        dp[0] = 0
        for i in range(n+1):
            for coin in coins:
                if i + coin <= n:
                    dp[i+coin] = min(dp[i+coin], dp[i] + 1)
        return dp[n] if dp[n] != math.inf else -1

# 代码技巧

# 真的需要冗余空间吗

有的题可以不需要冗余空间，但通常会导致代码很挫，以 1143 题为例。

1143 不开辟冗余空间

class Solution:
    def longestCommonSubsequence(self, a: str, b: str) -> int:
        if not a or not b: return 0
        n, m = len(a), len(b)
        dp = [[0]*m for _ in range(n)]
        for i in range(n):
            for j in range(m):
                if i == 0 and j == 0: dp[i][j] = 1 if a[i] == b[j] else 0
                elif i == 0: dp[i][j] = 1 if a[i] == b[j] else dp[i][j-1]
                elif j == 0: dp[i][j] = 1 if a[i] == b[j] else dp[i-1][j]
                elif a[i] == b[j]: dp[i][j] = dp[i-1][j-1] + 1
                else: dp[i][j] = max(dp[i-1][j], dp[i][j-1])
        return dp[n-1][m-1]

# Python DP 下标技巧

Python 的下标可以为 -1，这就让 DP 的代码变得很优雅，DP 下标就不会错位了，我们以115. 不同的子序列 (opens new window)为例。

115 循环外初始化

class Solution:
    def numDistinct(self, s: str, t: str) -> int:
        n, m = len(s), len(t)
        dp = [[0]*(m+1) for _ in range(n+1)]
        for j in range(-1, m): dp[-1][j] = 0
        for i in range(-1, n): dp[i][-1] = 1
        for i in range(n):
            for j in range(m):
                # s[i] t[j] dp[i][j] 不会错位
                if s[i] == t[j]: dp[i][j] = dp[i-1][j-1] + dp[i-1][j]
                else: dp[i][j] = dp[i-1][j]
        return dp[n-1][m-1]

115 循环内初始化

class Solution:
    def numDistinct(self, s: str, t: str) -> int:
        n, m = len(s), len(t)
        dp = [[0]*(m+1) for _ in range(n+1)]
        for i in range(-1, n):
            for j in range(-1, m):
                if j == -1: dp[i][j] = 1
                elif i == -1: dp[i][j] = 0
                # s[i] t[j] dp[i][j] 不会错位
                elif s[i] == t[j]: dp[i][j] = dp[i-1][j-1] + dp[i-1][j]
                else: dp[i][j] = dp[i-1][j]
        return dp[n-1][m-1]

# 题型

# 最长递增子序列

300. 最长递增子序列 (opens new window)是原题。

368. 最大整除子集 (opens new window)采用了类似的思想。

300 题

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

368 题

class Solution(object):
    def largestDivisibleSubset(self, nums):
        """
        :type nums: List[int]
        :rtype: List[int]
        """

        if not nums: return nums
        if len(nums) == 1: return nums
        l = len(nums)
        nums.sort()

        dp = [[i] for i in nums]
        
        for i in range(1, l):
            for j in range(i-1, -1, -1):
                if nums[i]%nums[j] == 0:
                    dp[i] = max(dp[j] + [nums[i]], dp[i],key=len)

        return max(dp,key=len)

# 更多习题

120. 三角形最小路径和 (opens new window)
152. 乘积最大子数组 (opens new window)
300. 最长上升子序列 (opens new window)，这题弄清楚 O(NlogN) 解法的心路历程有助于理解 DP 的本质
62. 不同路径 (opens new window)，还有一个数学解法
63

爬楼梯、硬币兑换系列：

70. 爬楼梯 (opens new window)，最简单的 DP 问题
746. 使用最小花费爬楼梯 (opens new window)
面试题 08.01. 三步问题 (opens new window)
403. 青蛙过河 (opens new window)，这题状态空间不是数组，转移方程也不是标准 DP，所以这是道难题
变形：可跨越步数由数组传入
变形：三步问题 + 相邻步数不能相同
变形：可跨越步数由数组传入 + 相邻步数不能相同

股票买卖系列，这个系列都是很规整的 DP：

字符串相关，这个系列的 DP 很不规整，导致题目很难做需要灵感：

正则系列：

44. 通配符匹配 (opens new window)
10. 正则表达式匹配 (opens new window)，比 44 题难一点

回文串系列：

647. 回文子串 (opens new window)