博客

动态规划是通过组合子问题的解来求解原问题。与分治方法不同的是，动态规划应用于子问题重叠的情况，即不同的子问题具有公共的子子问题。在这种情况下，分治策略会重复的计算那些公共子问题。而动态规划是对每个子子问题只求解一次，将其保存在一个表格中，从而避免重复计算这些问题。

动态规划通常用于求解最优化问题（optimization problem）。这类问题拥有多个解，我们希望从中计算出最优解。当然，有些问题可能会不止一个最优解，此时，我们只需按照需求或计算一个最优解，或计算出所有的最优解。

通常有4个步骤设计一个动态规划算法。

1. 刻画一个最优解的结构特征；
2. 递归的定义最优解的值；
3. 计算最优解的值，通常有两种方法，自底向上和自顶向下。
4. 利用计算出的信息构造一个最优解。

钢条切割的例子

给定一个长度为n英寸的钢条和一个价格表











p






i







(


i


=


1


,


2


,


.


.


.


n


)










$p_i(i=1,2,...n)$
,求切割钢条的方案，使得销售收益











r






n















$r_n$
最大。

假设切割长度与价格表如下所示

因为在钢条左端








i


(


i


=


1


,


2


,


.


.


.


n


−


1


)










$i(i=1,2,...n-1)$
处可以选择切割和不切割两种方式，所以长度为








n










$n$
的钢条共有












2






(







n


−


1


)











$2^(n-1)$
中切割方案。当








n


=


4










$n=4$
时，即有一个长度为4 的钢条，怎样切割才能获得最大收益。可以有8中方案，如下。

• 4 = 4 , 收益
  
  
  
  
  
  
  
  
  r
  
  
  =
  
  
  9
  
  
  
  
  
  
  
  
  
  
  $r=9$
• 4 = 1+3，收益为