动态规划（一）
动态规划开胃菜
动态规划中有几个重要概念，分别是
- 状态转移方程
- 重叠子问题
递推与动态规划
先来做一道高中数学题
通俗来讲动态规划 算法并不直接给出最终结果的求解表达式，而是通过找到问题规模之间的 动态转移方程，借此不断缩小问题规模，逐渐迫近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) quadleft(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 总结一下，当出现重叠子问题时，自定向下的解法一需要备忘录来剪枝，自底向上的解法二需要状态压缩减少空间开销。
一般来说，自顶向下的方法如果不用备忘录剪枝，一般会超时。自底向上的方法不进行状态压缩一般也没事。
