常规算法介绍的差不多,最不喜欢的动态规划 Dynamic Programming 还是来啦,前面介绍贪心算法时以及一些最大最小收益等等的问题,其实都可以套用动态规划的思路来实现的,下面我们看看动态规划的思路与模版要点。
分治、递归、回溯以及本节的动态规划都有相似之处,介绍动态规划前我们再继续回顾下前面的数据结构以及模版,这些都要做到不断地重复不断地重复,有相关的问题直接模版就能够出来,再修改细节。?
- terminator 终止条件
- process 当前层处理逻辑
- drill down 到下一层继续处理
- restore 需要回复一些状态变量
同理,分治也有其模版套路,主要是 Split Sub Problem 以及 Merget Sub Problem。同样有其对应的终止条件,一般是子问题无法再向下细分时的最小问题,最终将多个 sub result 进行合并得到全局的 result。
- terminator 终止条件
- split 大问题拆分为小问题
- conquer 分别递归将小问题继续拆分
- merge 合并多个 sub_result 结果
动态规划 DP 也是在一定分治的基础上寻找最优子结构的过程。中间这句英语的意思是 '将一个复杂的问题分解成一个简单的子问题',这个也印证了前面说的分治。而最优子结构则是 DP 算法一般用于求解最优路线、最短路线、最值等等,其需要存储一个最优的状态并不断更新。
这里本质上其实和递归分治没有太大区别,核心都是找到问题的重复性并不断尝试,同时最优子结构可以做到在比较中淘汰不好的留下更好的。?
斐波那契数列:?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) 这样,以后遇到问题也可以想想自下而上的思路是否可行。
不同路径:?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 个位置放 👉🏻,直接套用组合公式即可。
不同路径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,我们一步一步加回去即可。每个题都没有固定的解法,还是不能养成惯性思维。
最长公共子序列:?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 之间的转换关系:
三角形最小路径和:?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 是先自顶而下,再从下逐渐返回结果。
动态规划的题目主要涉及到最优、 子问题等不方便穷举出所有可能的结果的问题。说只要涉及子序列问题,十有八九都需要动态规划来解决,往这方面考虑就对了。注意在 DFS 的过程中适当添加缓存,即空间换时间或者采用剪枝策略,因为 DP 在不优化的情况下,复杂度往往是指数级。