所以原本我们要求长度为 n 的钢条的最大收益，改成先求 n 个子问题：ri+r(n-i) (i=1..n) 。子问题形式完全一样，但规模更小。pn 就是 i=n 时的情况。
rn = max(pi+r(n-i)) i=1..n
自顶向下递归实现：
CUT-ROD(p, n):
if n == 0: return 0
q = -∞
for i = 1 to n:
q = max(q, p[i] + CUT-ROD(p, n-i))
return q
长度为 n 时，CUT-ROD 函数调用了多少次？2^n 次
带备忘的自顶向下
在上边朴素的递归实现中，如果每次我们保存每个子问题的解，下次就不用再计算了。这就是备忘的意思。
MEMOIZED-CUT-ROD(p, n)
let r[0..n] be a new array
for i = 0 to n
r[i] = -∞
return MEMOIZED-CUT-ROD-AUX(p, n, r)
MEMOIZED-CUT-ROD-AUX(p, n, r)
if r[n] >= 0
return r[n]
if n == 0
q = 0
else
q = -∞
for i = 1 to n
q = max(q, p[i] + MEMOIZED-CUT-ROD-AUX(p, n-i, r)
r[n] = q
return q
自底向上
将子问题按规模排序，由小至大逐一求解。因为小的问题都算过了，当我们算到最后时，整个问题就解完了。
自底向上不用递归调用函数，只需一个循环来解决问题，通常来说会比自顶向下更快。
BOTTOM-UP-CUT-ROD(p, n)
let r[0..n] be a new array
r[0] = 0
for j = 1 to n
q = -∞
for i = 1 to j
q = max(q, p[i] + r[j-i])
r[j] = q
return r[n]
时间复杂度，算了 n^2 次。
练习
15.1-5
def fib(n):
f = [ 0, 1]
for i in range(2, n):
f.append(f[i-1] + f[i-2])
return f[n-1]
英文是 dynamic programming
其中的 programming 不是编程的意思。最早提出 dynamic programming 是 Richard Bellman 在 1955 年提出，那个时候还没有编程这个概念，其中的 programming 是指一种用表格解决问题的方法。
动态规划的解题方法与分治法有些类似，都是把问题划分为子问题来求解。但不同的是：
如果一个问题分解为很多子问题，而这些子问题都不相交，此时可以用分治法。
而如果一个问题分解成的子问题有重叠，那么用分治法就会反复的计算那些相同的子问题。而动态规划只对每个子问题求解一次，把它的解放在一个表格中，下次就不用再计算相同的问题了。
钢条切割问题
分析：
长度为 n 的钢条，可以切的点有 n-1 个，每个点有两种选择（可切、可不切），所以共有 2^(n-1) 种切法。
rn 是长度为 n 的钢条的最大化收益。 r(n-1) 是长度为 n-1 的钢条的最大化收益。 ...
对于长度为 n 的钢条，它的最大化收益是以下值中最大的：
所以 rn = max(pn, r1+r(n-1), r2+r(n-2), ... , r(n-1)+r1)
所以原本我们要求长度为 n 的钢条的最大收益，改成先求 n 个子问题：ri+r(n-i) (i=1..n) 。子问题形式完全一样，但规模更小。pn 就是 i=n 时的情况。
rn = max(pi+r(n-i)) i=1..n
自顶向下递归实现：
长度为 n 时，CUT-ROD 函数调用了多少次？2^n 次
带备忘的自顶向下
在上边朴素的递归实现中，如果每次我们保存每个子问题的解，下次就不用再计算了。这就是备忘的意思。
自底向上
将子问题按规模排序，由小至大逐一求解。因为小的问题都算过了，当我们算到最后时，整个问题就解完了。
自底向上不用递归调用函数，只需一个循环来解决问题，通常来说会比自顶向下更快。
时间复杂度，算了 n^2 次。
练习
15.1-5
动态规划原理
最优子结构 子问题重叠