By

Contents
  1. 1. 钢条切割问题
  2. 2. 简单的递归求解
  3. 3. 使用动态规划
    1. 3.1. 带备忘的自顶向下
    2. 3.2. 自底向上
  4. 4. 小结

动态规划很像分治法，都是通过分解成子问题并结合其结果来得到原问题的解。区别在于法的子问题不相交，但是动态规划的子问题是重叠的。

动态规划通常用来求解最优解问题，即在问题的众多可行方案中找出一个（不唯一）最优解。

钢条切割问题

将长度为n的钢条切割成若干短钢条出售，切割成本不计，钢条长度与售价关系如下表，求一种售价最大的切割法（含不切割情况）。

简单的递归求解

r(n)表示规模为n问题的最优解，p(i)为长i钢条的售价：

以下为Python的代码实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
p=[0,1,5,8,9,10,17,17,20,24,30]
def cut_rod(n,p):
    if n == 0:
        return 0
    q=-1
    for i in range(1,n+1):
        t= p[i]+cut_rod(n-i,p)
        if t > q:
            q=t
    return q
print cut_rod(9,p)

运行结果为25

但是这种方法对同样的规模的问题进行了多次重复的运算，即对2^(n-1)种切割都进行了计算，规模越小的问题重复次数越多，性能很差，时间性能为O(2^n).

使用动态规划

动态规划仔细安排求解，对每个子问题只求解一次，将结果保存，用额外的空间换取时间。有两种等价的实现方式：

带备忘的自顶向下

仍然按自然的递归形式编写过程，但过程中保存每个子问题的解，遇到子问题时先从存档中查找，若无记录再计算。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
def cut_rod_mem(n, p):
    m = [0]
    for i in range(10):
        m.append(-1)
    def inner(n, p):
        if m[n]!=-1:
            return m[n]
        for i in range(1, n + 1):
            t = p[i] + inner(n - i, p)
            if t > m[n]:
                m[n] = t
        return m[n]
    return inner(n,p)

自底向上

可以将子问题按规模排序，由小到进行求解，确保每次求解更小的子问题已有存档。

1
2
3
4
5
6
7
8
9
10
11
def bottom_up(n, p):
    m = [0]
    for i in range(10):
        m.append(-1)
    for i in range(1, n + 1):
        for j in range(1, i + 1):
            t = p[j] + m[i - j]
            if t > m[i]:
                m[i] = t
    return m[n]

以上两种方法的渐近时间是一样的，为多项式级性能，只在特定的情形下有差异。由于bottom up的方法没有递归中频繁的函数调用开销，性能更好。

小结

这种问题的特性为

原问题可以分解为形式一致，但规模更小的子问题

子问题可以独立求解

子问题的解可组合成原问题的解

动态规划相较原始的递归不同在于：

仔细安排求解顺序，确保相同子问题只求解一次。

Contents
  1. 1. 钢条切割问题
  2. 2. 简单的递归求解
  3. 3. 使用动态规划
    1. 3.1. 带备忘的自顶向下
    2. 3.2. 自底向上
  4. 4. 小结