Lecture 13: Dynamic programming: overlapping subproblems, optimal substrcture
本课重点讲述了动态规划，介绍了其核心思想，即默记法。本课前半部分用斐波纳契数的例子详细介绍默记法的使用方法。后半部分介绍了决策树和用它解决0/1背包问题的两个程序样例。
动态规划(Dynamic programming)，根据百度百科所述，是运筹学的一个分支，是求解决策过程(decision process)最优化的数学方法。在20世纪50年代初，美国数学家R.E.Bellman（贝尔曼）等人在研究多阶段决策过程(multistep decision process)的优化问题时，提出了著名的最优化原理(principle of optimality)，把多阶段过程转化为一系列单阶段问题，利用各阶段之间的关系，逐个求解，创立了解决这类过程优化问题的新方法——动态规划。
动态规划最关键的地方在于，存在一种子问题和最理想子结构重叠的情况。这个说法非常抽象，但简单来说就是如果子问题的最优解被重复使用的话，我们就可以使用动态规划。下面就举一个例子来详细解释：
在Lecture 4的时候，有一个例子斐波那契数Fibonacci numbers，当时有如下程序：
def Fib(n):
if n == 1 or n == 0:
return 1
else:
return Fib(n - 1) + Fib(n - 2)
那么，如果要计算Fib(5)的结果，我们会用到Fib(4)和Fib(3)的结果，而Fib(4)又用到了Fib(3)和Fib(2)的结果，依此类推。我们会发现，Fib(3)，Fib(2)的结果被多次调用，而我们又需要花时间去计算Fib(3)和Fib(2)，那么这就造成了累赘计算。
相信到这里，大家都会这样觉得，为什么不把这些结果存下来，这样以后用到的时候就可以直接使用了呢？没错，这就是我们所说的默记法。
默记法(Memorization)是动态规划的核心内容。具体方法如下：
- 我们在第一次计算的时候就记录一个值
- 然后再后续的问题中使用这个值
这个概念非常简单，容易理解。那么对于上面的斐波那契的例子，我们就可以运用默记法，标程如下：
def FastFib(n, memo):
if not n in memo:
memo[n] = FastFib(n - 1, memo) + FastFib(n - 2, memo)
return memo[n]
def FastFibonacci(n):
memo = {0:1, 1:1} # initialize the memo
return FastFib(n, memo)
本课的后半部分则讲了0/1背包问题的两个解法，下面例1是普通解法，只是用了简单的决策树，而例2则用了动态规划，优化了例1。两个例子如下：
例1：普通解法
def maxVal(w, v, i, aW):
if i == 0:
if w[i] <= aW:
return v[i]
else:
return 0
without_i = maxVal(w, v, i-1, aW)
if w[i] > aW:
return without_i
else:
with_i = v[i] + maxVal(w, v, i-1, aW - w[i])
return max(with_i, without_i)
例2：动态规划
def fastMaxVal(w, v, i, aW, m):
try:
return m[(i, aW)] # to check whether the thing is in the memo or not
except KeyError:
if i == 0:
if w[i] <= aW:
m[(i, aW)] = v[i]
return v[i]
else:
m[(i, aW)] = 0
return 0
without_i = fastMaxVal(w, v, i-1, aW, m)
if w[i] > aW:
m[(i, aW)] = without_i
return without_i
else:
with_i = v[i] + fastMaxVal(w, v, i-1, aW - w[i], m)
res = max(with_i, without_i)
m[(i, aW)] = res
return res
def MaxVal0(w, v, i, aW):
m = {}
return fastMaxVal(w, v, i, aW, m)
这个程序的算法复杂度为O(ns)，n为可选择物品的总数量，s为背包可以装的物品数量。这个算法不仅需要O(ns)的时间，也需要O(ns)的空间。可以说，这也是一个用空间换时间的算法。
那么我们再来从复杂度的方面考虑动态规划。根据百度资料，能用动态规划解决的问题，肯定能用搜索解决。但是搜素时间复杂度太高了，怎么优化呢？我们就想到了记忆化搜索，也就是默记法，就是搜完某个解之后把它保存起来，下一次搜到这个地方的时候，调用上一次的搜索出来的结果。这样就解决了处理重复状态的问题。
动态规划之所以速度快是因为解决了重复处理某个状态的问题。记忆化搜索是动态规划的一种实现方法。
搜索到i状态，首先确定要解决i首先要解决什么状态。那么那些状态必然可以转移给i状态。于是我们就确定了状态转移方程。然后我们需要确定边界条件。将边界条件赋予初值。此时就可以从前往后枚举状态进行状态转移拉。
（以上三段均来自于百度：http://zhidao.baidu.com/question/407709820.html）
总结：详细介绍了动态规划和其核心内容默记法，非常有用，初学者必看！
学员评论