动态规划第一讲
把难题放一边，先来理解动态规划中的一些重要概念
- 状态转移方程
- 重叠子问题
- 备忘录剪枝
- 状态压缩
1.1递推与动态规划
要理解动态规划的基本解题思路，先来做一道高中数学题
通俗来讲动态规划 算法并不直接给出最终结果的求解表达式，而是通过找到问题规模之间的 动态转移方程，借此不断缩小问题规模，逐渐迫近base case。所谓动态转移方程就是不同规模问题之间的关系，类似递推式。
1.1.1自顶向下解法
def func(n):
if n == 0:
return 2
return func(n - 1) + 3
所谓自定向下解法就是使用函数递归，递归的计算过程正如上图紫线箭头方向
1.1.2 自底向上解法
def func2(n):
# 确定dp[i] 的含义
# d[i] == func(i)
# dp数组规模,规模与dp[i]的定义密切相关
# 根据dp[i] 定义，func2(n) 对应dp[n]
# 要使得dp[n] 合法，数组长度要为 n+1
dp = [0] * (n + 1)
# base_case
dp[0] = 2
# dp数组的遍历顺序
# func(i) = func(i-1) + 3
# dp[i] = dp[i-1] + 3
for i in range(1, n + 1):
dp[i] = dp[i - 1] + 3
return dp[n]
所谓自底向上解法就是利用一个数组存储计算过程产生的值，计算过程正如上图绿色箭头方向
1.2重叠子问题
直观了解了状态转移方程后，以斐波那契额数列问题为例看重叠子问题。
F(0)=0,F(1)=1,F(n)=F(n−1)+F(n−2)(n≥2,n∈N∗)
1.2.1自顶向下解法
def fib(n):
if n == 0:
return 0
elif n == 1:
return 1
return fib(n - 1) + fib(n - 2)
1.2.2 观察重叠子问题
def fib(n):
# 查看函数调用次数，看见”重叠子问题“
print("函数调用func(", n, ")")
if n == 0:
return 0
elif n == 1:
return 1
return fib(n - 1) + fib(n - 2)
python3 test.py | grep "( 0 )" -c
4181
python3 test.py | grep "( 10 )" -c
89
python3 test.py | grep "( 15 )" -c
8
python3 test.py | grep "( 20 )" -c
1
不难发现， fib(0) 被执行了4181次，fib(10) 被执行了89次，fib(15) 被执行了8次。。。
重叠子问题导致了大量的重复计算。并且重复的计算量随着问题规模增大极速上升。
因此，使用备忘录 来减少重复计算非常有必要！
1.2.3 自顶向下 + 备忘录
# 使用一个字典存储计算过得fib(n)
# base_case 也可直接放入备忘录
# 字典以 n为键，fib(n) 为值
memo = {0: 0, 1: 1}
def fib1(n):
# 如果备忘录中有记载，直接返回
print("函数调用func(", n, ")")
if n in memo.keys():
return memo[n]
val = fib1(n - 1) + fib1(n - 2)
memo[n] = val
return val
python3 try.py
函数调用func( 20 )
函数调用func( 19 )
函数调用func( 18 )
函数调用func( 17 )
函数调用func( 16 )
函数调用func( 15 )
函数调用func( 14 )
函数调用func( 13 )
函数调用func( 12 )
函数调用func( 11 )
函数调用func( 10 )
函数调用func( 9 )
函数调用func( 8 )
函数调用func( 7 )
函数调用func( 6 )
函数调用func( 5 )
函数调用func( 4 )
函数调用func( 3 )
函数调用func( 2 )
备忘录相当于为整个递归遍历树进行了一个剪枝操作。
1.2.4 自底向上
def fib2(n):
# 确定dp[i]的含义
# dp[i] = fib(i)
# dp数组规模
dp = [0] * (n + 1)
# base_case
dp[0] = 0
dp[1] = 1
# dp 数组遍历方向
# fib(i) = fib(i-1) + fib(i-2)
# dp[i] = dp[i-1] + dp[i-2]
# dp[大] 依赖 dp[小] 所以先算dp[小]
for i in range(2, n + 1):
dp[i] = dp[i - 1] + dp[i - 2]
return dp[n]
使用dp数组自顶向下来解不存在 重叠子问题。
空间开销为 O(n)，不难看出，每次计算新值只依赖前面两个值。因此我们可以使用两个变量来记录，而不使用dp数组。
1.2.5 自底向上 + 状态压缩
def fib3(n):
if n == 0:
return 0
if n == 1 or n == 2:
return re1
# prev初始为dp[1]
prev = 1
# curr初始为dp[2]
curr = 1
# 注意迭代次数
# 注意i = 3时，迭代了1轮，迭代结束 curr == dp[3]
# 注意i = 4时，迭代了2轮，迭代结束 curr == dp[4]
# 所以 i = n 时，迭代结束时 curr == dp[n]
# range 前闭后开 so ...
for i in range(3, n + 1):
sum = prev + curr
prev = curr
curr = sum
return curr
当出现重叠子问题时，自定向下的解法一需要备忘录来剪枝，自底向上的解法二需要状态压缩减少空间开销。
一般来说，自顶向下的方法如果不用备忘录剪枝，一般会超时。自底向上的方法不进行状态压缩一般也没事。
1.3总结
| 自顶向下 | 自底向上 | |
|---|---|---|
| 编程方式 | 递归 | 数组 |
| 额外辅助 | 备忘录，用于剪枝 | 状态压缩 |
| 若不使用辅助 | 一般超时，重复子问题往往指数级增加计算量 | 一般没事，一些情况也不容易状态压缩。不压缩往往是O(n)、 O(n^2) 空间复杂度 |