一.引言
常规算法介绍的差不多，最不喜欢的动态规划 Dynamic Programming 还是来啦，前面介绍贪心算法时以及一些最大最小收益等等的问题，其实都可以套用动态规划的思路来实现的，下面我们看看动态规划的思路与模版要点。
二.动态规划的简介
1.递归 Recur
分治、递归、回溯以及本节的动态规划都有相似之处，介绍动态规划前我们再继续回顾下前面的数据结构以及模版，这些都要做到不断地重复不断地重复，有相关的问题直接模版就能够出来，再修改细节。
- terminator 终止条件
- process 当前层处理逻辑
- drill down 到下一层继续处理
- restore 需要回复一些状态变量
2.分治 Divide Conquer
同理，分治也有其模版套路，主要是 Split Sub Problem 以及 Merget Sub Problem。同样有其对应的终止条件，一般是子问题无法再向下细分时的最小问题，最终将多个 sub result 进行合并得到全局的 result。
- terminator 终止条件
- split 大问题拆分为小问题
- conquer 分别递归将小问题继续拆分
- merge 合并多个 sub_result 结果
3.动态规划 DP
动态规划 DP 也是在一定分治的基础上寻找最优子结构的过程。中间这句英语的意思是 '将一个复杂的问题分解成一个简单的子问题'，这个也印证了前面说的分治。而最优子结构则是 DP 算法一般用于求解最优路线、最短路线、最值等等，其需要存储一个最优的状态并不断更新。
这里本质上其实和递归分治没有太大区别，核心都是找到问题的重复性并不断尝试，同时最优子结构可以做到在比较中淘汰不好的留下更好的。
3.经典算法实战
1.Fib [509]
斐波那契数列: https://leetcode.cn/problems/fibonacci-number/description/
◆ 题目分析
典中典的题目，分治回溯的鼻祖，这里我们别使用之前的方法和基于 DP 的方法进行解答，正所谓经不经典我不管，我只需要这一款啊。
◆ 双指针实现
class Solution(object):
def fib(self, n):
"""
:type n: int
:rtype: int
"""
a, b = 0, 1
# 向右移动
for i in range(n):
a , b = b, a+b
return a前面介绍过很多次了，这里不再赘述，下面看下 DP 的思路。
◆ DP 实现
class Solution(object):
def fib(self, n):
"""
:type n: int
:rtype: int
"""
cache = {0:0, 1:1}
return self.fib_by_dp(n, cache)
def fib_by_dp(self, n, cache):
if n not in cache:
cache[n] = self.fib_by_dp(n-1, cache) + self.fib_by_dp(n-2, cache)
return cache[n]DP 就是在实现过程中存储状态变量并更新至最优，我们这里最优其实就是到达最终目标值即可。
上面的图可以看到，直接 f(n-1) + f(n-2) 计算时，随着 level 的增加，需要计算的问题呈指数级展开，采用缓存后，问题得到剪枝，只需要 o(n) 的时间复杂度即可。
不过这个方法由于加入了 cache 的 dict，所以空间复杂度相较之前的方案有一定增加，但执行速度上大同小异。 第一种方法其实是一种自下而上的思维，而下面的方法则是自上而下，在过程中添加缓存。我们的人脑一般多是下面这种思维结构，拿到问题 f(n) 然后 f(n-1) 这样，以后遇到问题也可以想想自下而上的思路是否可行。
2.Unique-Paths [62]
不同路径: https://leetcode.cn/problems/unique-paths
◆ 题目分析
对于第一行和第一列的所有位置，机器人只有1种走法可以到达，一路向南和一路向东，所以这两路都标注为 1，其余每个位置的走法都等于其上面和左边走法之和，对于 (1,1) 这个点，可以 (1,0) -> (1,1) 也可以 (0, 1) -> (1,1)，所以其走法等于二者之和，其余的点同理。
◆ DP 实现
class Solution(object):
def uniquePaths(self, m, n):
"""
:type m: int
:type n: int
:rtype: int
"""
# m 行 n 列的矩阵
mat = [[1] * n]
for i in range(m-1):
mat.append([1] + [0] * (n-1))
# 进行累加
for i in range(1, m):
for j in range(1, n):
mat[i][j] = mat[i-1][j] + mat[i][j-1]
return mat[m-1][n-1]按照上面的思路，初始化行和列的 1 后，向左右累加即可。
◆ DP 实现 - 内存优化
class Solution:
def uniquePaths(self, m, n):
# m 行 n 列的矩阵
cur, next = [1] * n, [1] * n
# 进行累加
for i in range(1, m):
for j in range(1, n):
next[j] = cur[j] + next[j - 1]
cur = next[:]
return next[-1]
上面我们 for i in range(n) 遍历行，起始有上下两行的内存即可，相当于双指针不断向下走即可。运行速度和上面一致，但是内存节省了很多。上面提到了自上而下和自下而上，对于本题这个思想也适用，机器人从左上角到右下角终点有多少种走法，右下角终点到机器人所在起点就有多少种回去的方法，有兴趣的同学也可以反过来实现一遍，体会这两种思维方式。
◆ 排列组合
class Solution(object):
def uniquePaths(self, m, n):
"""
:type m: int
:type n: int
:rtype: int
"""
re = 1
st = m + n - 2
down = 1
for i in range(1, n):
re *= st
st -= 1
down *= i
return re // down这个题还有一个思路就是使用排列组合，对于一个 mxn 的网格，机器人想要到达终点一点要向下 n-1 步，向右 m - 1 步，所以可以看作是组合问题，M+N-2 个格子，n-1 个放 👇🏻，m-1 个位置放 👉🏻，直接套用组合公式即可。
3.Unique-Paths 2 [63]
不同路径2: https://leetcode.cn/problems/unique-paths-ii/
◆ 题目分析
与上题目标一致，是机器人从 A 点到 B 点，区别是这次添加了障碍物，当遇到障碍物时，此路为死路，此时路径的可能性就不是其上面和左面的和了，而是 0。
◆ 动态规划
class Solution(object):
def uniquePathsWithObstacles(self, obstacleGrid):
n = len(obstacleGrid)
m = len(obstacleGrid[0])
dp = [0] * m
#起点可能有障碍物
dp[0] = 1 if obstacleGrid[0][0] == 0 else 0
for i in range(n):
for j in range(m):
#有障碍物的格子直接赋0
if obstacleGrid[i][j] == 1:
dp[j] = 0
#否则dp[j]的值由左方和上一次迭代的dp[j]累加而来
elif obstacleGrid[i][j] == 0 and j - 1 >= 0:
dp[j] = dp[j] + dp[j - 1]
return dp[-1]对于 [i][j] == 1 的障碍物格子，其值为 0 不会有走法走到这里。
◆ 递归实现
class Solution(object):
def uniquePathsWithObstacles(self, obstacleGrid):
m = len(obstacleGrid)
n = len(obstacleGrid[0])
d = {}
def dfs(i, j):
if (i,j) in d:
return d[i,j]
#边界/障碍物检查
if i >= m or j >= n or obstacleGrid[i][j] == 1:
return 0
#达到重点了
if i == m - 1 and j == n - 1:
return 1
#继续往右(i,j+1)、往下(i+1,j)递归调用
d[i,j] = dfs(i + 1, j) + dfs(i, j + 1)
return d[i,j]
return dfs(0, 0)
这个思路就是自底向上的，终点不会有障碍物，其值为 1，我们一步一步加回去即可。每个题都没有固定的解法，还是不能养成惯性思维。
4.LCS [1143]
最长公共子序列: https://leetcode.cn/problems/longest-common-subsequence
◆ 题目分析
最长公共子序列是典型的动态规划问题，对于字符串 s 和 t 而言，其有两种情况，如果两个索引位置的字符相同，子序列公共部门 +1，然后计算 s[i-1] 和 t[j-1] 的最长公共子串即可，如果二者不相等，则最长公共子串需要判断两个方向，要么 s[i-1] 和 t[j] 或者 s[i] 和 t[j-1]:
◆ 动态规划
class Solution(object):
def longestCommonSubsequence(self, text1, text2):
"""
:type text1: str
:type text2: str
:rtype: int
"""
m, n = len(text1), len(text2)
# 构建 m+1 x n+1 的网格
dp = [[0] * (n+1) for _ in range(m+1)]
# 从 (1,1) 开始，防止越界
for i in range(1, m+1):
for j in range(1, n+1):
if text1[i - 1] == text2[j - 1]:
dp[i][j] = dp[i-1][j-1] + 1
else:
dp[i][j] = max(dp[i-1][j], dp[i][j-1])
return dp[m][n]下图展示了如何通过状态转移计算 s 与 t 的最长公共子串长度。 当我们遇到子序列类型的问题，穷举出所有可能的结果都不容易，而动态规划算法做的就是穷举 + 剪枝，它俩天生一对儿。所以可以说只要涉及子序列问题，十有八九都需要动态规划来解决，往这方面考虑就对了。
◆ 暴力解法
class Solution(object):
def longestCommonSubsequence(self, text1, text2):
"""
:type text1: str
:type text2: str
:rtype: int
"""
m, n = len(text1), len(text2)
def dfs(i, j):
# str = "" 的 bad case
if i == -1 or j == -1:
return 0
if text1[i] == text2[j]:
# 一样就都截取一个字符
return dfs(i - 1, j - 1) + 1
else:
# 取更大的可能
return max(dfs(i - 1, j), dfs(i, j - 1))
return dfs(m - 1, n - 1)这个思路其实就是最原始的解法，但是遍历的情况很多会导致运行超时，所以才有了上面我们使用 DP Table 进行缓存的方法，这里动态规划要学会使用缓存结果，构建 i/j 之间的转换关系:
5.Triangle [120]
三角形最小路径和: https://leetcode-cn.com/problems/triangle/description/
◆ 题目分析
根据最下层的 m 个数，可以遍历更新上一层 m-1 个数里的最小值，持续向上更新即可。
◆ 自下而上 DP
class Solution(object):
def minimumTotal(self, triangle):
"""
:type triangle: List[List[int]]
:rtype: int
"""
" re = min([row, j], [row, j+1]) "
dp = triangle
for i in range(len(triangle) - 2, -1, -1):
for j in range(len(triangle[i])):
# 每一个位置，都更新为其最小值
dp[i][j] += min(dp[i+1][j], dp[i+1][j+1])
return dp[0][0]
◆ 自上而下 DFS
class Solution(object):
def minimumTotal(self, triangle):
"""
:type triangle: List[List[int]]
:rtype: int
"""
" re = min([row, j], [row, j+1]) "
#
row = len(triangle)
cache = {}
def dfs(level, col, triangle):
# 有缓存直接返回
if ((level, col) in cache):
return cache[(level, col)]
# 到达最后一层了
if (level == row - 1):
return triangle[level][col]
# 获取分叉的两个值
left = dfs(level + 1, col, triangle)
right = dfs(level + 1, col + 1, triangle)
# 增加 Cache
cache[(level, col)] = min(left, right) + triangle[level][col]
return cache[(level, col)]
return dfs(0, 0, triangle)在暴力 DFS 的基础上，增加了 Cache 存储，不过效率一般，思路其实也是从下而上求最小，但是 DFS 是先自顶而下，再从下逐渐返回结果。
6.Max-Sub-Array[53]
最大子数组和: https://leetcode.cn/problems/maximum-subarray/
◆ 题目分析
假设我们的问题结果为 F(i) 代表以当前索引处为结尾最大连续子数组，则其等于 F(i-1) + a[i]，即子问题的最大连续子数组 + 当前的值，这里需要考察 F(i-1) 的正负，如果其值 >0，则 F(i) = F(i-1) + a[i] 否则 F(i) = a[i]，因为前面最大的和都是负的，那还不如不加。
◆ 动态规划
class Solution(object):
def maxSubArray(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
for i in range(1, len(nums)):
# dp[i] = max(nums[i], dp[i-1] + nums[i])
# 最大子序列和 => 当前元素最大 or 之前+现在最大
nums[i] = max(nums[i], nums[i] + nums[i-1])
return max(nums)对应的 DP 转移方程为 dp[i] = max(nums[i], dp[i-1] + nums[i])，我们也可以把 nums[i] 抽出来，nums[i] = nums[i] + max(0, nums[i-1])，相当于位置 i 要看你左边是不是小于 0。
7.Max-Product-Sub-Array [152]
最大乘积子序列: https://leetcode.cn/problems/maximum-product-subarray/
◆ 题目分析
和上题类似，也是求最大子序列，只不过加法换做了乘法。此时如果我们还复用之前的状态公式: F(i) = F(i-1) * a[i] 就不对了，因为这里乘法可能存在负数，如果 F(i-1) < 0，而 a[i] > 0 或者有其他情况，这里的 F(i-1) 是推不到 F(i) 的，我们在考虑正数最大的情况下，还要考虑负数最小的情况，因为负负得正的问题，所以状态方程如下:
◆ 动态规划
class Solution(object):
def maxProduct(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
mi, ma, res = nums[0], nums[0], nums[0]
for i in range(1, len(nums)):
# mx、mn 为上一步的最大与最小
mx, mn = ma, mi
# 更新本次的最大、最小
ma = max(mx * nums[i], nums[i], mn * nums[i])
mi = min(mx * nums[i], nums[i], mn * nums[i])
res = max(ma, res)
return res根据当前值和上一轮的 max、min，更新当前的 max、min，并更新最终的 res。
◆ 动态规划-优化
class Solution(object):
def maxProduct(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
mi, ma, res = nums[0], nums[0], nums[0]
for i in range(1, len(nums)):
# mx、mn 为上一步的最大与最小
if nums[i] < 0:
ma, mi = mi, ma
# 更新本次的最大、最小
ma = max(ma * nums[i], nums[i])
mi = min(nums[i], mi * nums[i])
res = max(ma, res)
return res上面的方法每次比较三个数，通过判断当前值的正负，我们可以减少一个比较。这里如果 nums[i] 是正数，则大的更大小的更小，不用修改；反之，大的越小，小的越大，这样每次只需要比较两个数字即可。
8.Coin-Change [322]
硬币找零: https://leetcode-cn.com/problems/coin-change/description/
◆ 题目分析
每次可以选取不同的硬币，这里我们可以将其理解为一颗状态树，也可以进行动态的递归，下面我们介绍下两种方法。
◆ BFS
class Solution(object):
cur_min = 9999999999
def coinChange(self, nums, target, cur):
if target == 0:
self.cur_min = min(self.cur_min, len(cur[:]))
return
elif target < 0:
return
else:
for i in nums:
cur.append(i)
# 目标值减当前 coin，继续寻找
self.coinChange(nums, target - i, cur)
cur.pop()
return self.cur_min这里遍历完我们可以获得所有题目的子集解答，找到路径最短的数组即可。 该做法的时间复杂度为指数级，所以无法通过。
◆ 递归实现
class Solution(object):
def coinChange(self, coins, amount):
"""
:type coins: List[int]
:type amount: int
:rtype: int
"""
cache = {}
# 要凑金额 n，需要最少的结果
def dp(n):
if n in cache:
return cache[n]
# base case
if n == 0:
return 0
if n < 0:
return -1
res = float('INF')
for coin in coins:
sub = dp(n - coin)
if sub == -1:
continue
res = min(res, 1 + sub)
cache[n] = res if res != float('INF') else -1
return cache[n]
return dp(amount)
上面的方法进行了多次重复计算，这里我们增加 cache 记录提高计算速度。
◆ 动态规划
class Solution(object):
def coinChange(self, coins, amount):
"""
:type coins: List[int]
:type amount: int
:rtype: int
"""
# 初始化一个较大的值
dp = [amount + 1] * (amount + 1)
dp[0] = 0
for coin in coins: # 遍历硬币
for j in range(coin, amount + 1):
dp[j] = min(dp[j], dp[j-coin] + 1) # DP 方程
ans = dp[amount]
return ans if ans != amount + 1 else -1
前面 Fib 递推公式为 F(n) = F(n-1) + F(n-2)，这里我们可以考虑为:
F(n) = min(F(n-coin)+1 for coin in coins)
即 coins 对应的多个子问题的最小值加最后一个硬币即可。
四.总结
动态规划的题目主要涉及到最优、 子问题等不方便穷举出所有可能的结果的问题。说只要涉及子序列问题，十有八九都需要动态规划来解决，往这方面考虑就对了。注意在 DFS 的过程中适当添加缓存，即空间换时间或者采用剪枝策略，因为 DP 在不优化的情况下，复杂度往往是指数级。
