概述

　　前面我们已经介绍了分治思想。分治思想是将问题划分为互不相交的子问题，递归的求解子问题，再将它们的解组合起来，求出原问题的解。这一篇文章我们将一起来讨论一下动态规划。它是算法中另一个重要的思想。　
　　动态规划的思想与分治思想相反，动态规划是用于子问题重叠的情况，即不同的子问题具有相同的子子问题。在这种情况下，动态规划相对于分治算法的优势在于，分治算法会重复的计算本是相同的子子问题，导致运算时间的浪费，而动态规划则只会计算一次。
　　动态规划常常用于解决最优解的问题。这类问题常常有很多可行的解，我们希望的是从这些解中找到最优解。

简介

　　类似于分治算法的三个步骤，动态规划的思考和设计层面也具有四个步骤。

刻画一个最优解结构
递归定义最优解的值
计算最优解的值，通常使用自底向上的方法
利用计算出来的信息构造最优解

实践

　　这里我们通过一个简单的例子对动态规划的思想进行一下实践。

问题

长度i	1	2	3	4	5	6	7	8	9	10
价格Pi	1	5	8	9	10	17	17	20	24	30

　　上述表格描述的是一个钢条公司的钢条长度和价格的关系。它们希望得到给定长度为n的钢条，如何切割才能达到利益最大化。

分析

　　我们用n表示钢条的长度，i表示切割的长度，Pi表示切割长度对应的收益，Rn代表长度为n的钢条对应的最大收益。
　　则我们可以得出Rn=max(Pi + Rn-1)。这个推倒式的表明的是对于n长的钢条。进行i(i从1到n)的长度的切割，获得的切割收益与剩余收益的和。再从i=1到i=n中选取最大的值，就是该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]