动态规划开胃菜
动态规划中有几个重要概念，分别是
- 状态转移方程
- 重叠子问题
递推与动态规划
先来做一道高中数学题
通俗来讲动态规划 算法并不直接给出最终结果的求解表达式，而是通过找到问题规模之间的 动态转移方程，借此不断缩小问题规模，逐渐迫近base case
解法一
def func(n):
if n == 0:
return 2
return func(n - 1) + 3
自顶向下的计算顺序，正如上图紫线箭头方向
解法二
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]
自底向上解法，正如上图绿色箭头方向
重叠子问题
直观了解了状态转移方程后，接着来以斐波那契额数列问题为例看重叠子问题。
$ F(0)=0, \quad F(1)=1,\quad F(n)=F(n-1)+F(n-2) \quad\left(n \geq 2, \quad n \in N^{*}\right) $
解法一
def fib(n):
if n == 0:
return 0
elif n == 1:
return 1
return fib(n - 1) + fib(n - 2)
不难发现， fib(18) 被执行了两次，fib(17) 被执行了3次。fib(16) 被执行了4次。。。
计算过的问题我们不想重复计算，需要一个备忘录记录我们算过的fib(n)。
解法一 + 备忘录
# 使用一个字典存储计算过得fib(n)
# n为键，fib(n) 为值
memo = {}
def fib1(n):
# 如果备忘录中有记载，直接返回
if n in memo.keys():
return memo[n]
if n == 0:
return 0
elif n == 1:
return 1
val = fib(n - 1) + fib(n - 2)
memo[n] = val
return val
备忘录相当于为整个递归遍历树进行了一个剪枝操作。
fib(18) 被执行了1次，fib(17) 被执行了1次。fib(16) 被执行了1次。。。
解法二
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数组。
解法二 + 状态压缩
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
总结一下，当出现重叠子问题时，自定向下的解法一需要备忘录来剪枝，自底向上的解法二需要状态压缩减少空间开销。
一般来说，自顶向下的方法如果不用备忘录剪枝，一般会超时。自底向上的方法不进行状态压缩一般也没事。