动态规划之Rod cutting

动态规划和分而治之相似，不过分治法是将问题划分为没有依赖的子问题，使用递归来解决子问题然后将子问题合并，而动态规划划分的问题之间存在依赖覆盖关系，如果使用分治法来处理会有重复计算的问题导致效率较低，动态规划将已计算的结果存放在表中用来避免重复计算
动态规划一般有如下四个步骤：

刻画最优解的结构
递归地定义最优解的值
以自下而上的方式计算最优解的值
根据计算出的信息构造一个最优解

动态规划的要素

最优子结构
重叠子问题

Rod cutting

五金店的老板娘每次都是采购一个长长的钢管，然后将其切为一段段的小钢管售卖，被切的钢管是整数，对于一个长度为n的钢管，需要计算其最大收益 $r_n$
如下是价格表

价格表

假设钢管的长度n为4，有如下8种切法

其中c切法
4=2+2的总价格为10收益最大，即 $r_4=10$

长度为n的钢管有 $2^{n-1}$ 种不同的切法 ( $C_{n-1}^0+C_{n-1}^1+...+C_n^n$ )

可以发现对于长度为n的钢管，其最大收益 $r_n$ 满足：

$r_n=max(p_n,r_1+r_{n-1},r_2+r_{n-2},...,r_{n-1}+r_1)$

这个理解起来不难，整体最优解包含两个相关子问题的最优解，最大化来自这两个片段中的每一个的收益。我们认为钢管切割问题具有最优子结构：问题的最优解包含相关子问题的最优解

对于n=0时， $r_0=0$ ,这个公式可以进一步简化为

$r_n=\underset{1\leq i \leq n} {max}(p_i+r_{n-i})$

这个公式是站在另一个视觉上看问题，钢管切割问题第一段切割长度为i和剩余的n-i长度规模钢管切割构成的子问题的和，第一段切割长度为i，对应的价格是 $p_i$ ,剩余的n-i长度看成是一个子问题最大收益为 $r_{n-i}$ ,所以 $r_n$ 是这两者的和

分治法实现

对于如上的推导公式，可以给出如下递归实现的分治法伪代码：

 cutRod(p,n)
    if n==0
      return 0
    q=-1
    for i=1 to n
        q=max(q,p[i]+cutRod(p,n-i))
  return q

上述代码的时间复杂度为

2^n

,效率比较低

动态规划实现

因此，动态编程使用空间换时间，它提供了一个time-memory trade-off的例子。节省的时间可能是巨大的：可能将指数级别的空间复杂度转为多项式级别的空间复杂度

通常有两种等价的方法来实现动态规划。我们将用我们的Rod cutting例子来说明：

第一种是top-down with memoization，在这种方法中，我们以自然的方式递归地编写过程，但保存每个子问题的结果（通常在数组或哈希表中）。这个过程现在首先检查它是否已经解决了这个子问题。如果是，则返回已保存的值，从而基于已保存的值进一步的计算；如果不是，则过程以通常的方式计算该值。
第二种方法是bottom-up method的方法。这种方法通常依赖于子问题“大小”的一些自然概念，因此解决任何特殊的子问题只依赖于解决“较小”的子问题。我们按大小对子问题进行排序，然后按大小顺序（最小优先）求解它们。在解决一个特定的子问题时，我们已经解决了它的解决方案所依赖的所有较小的子问题，并且保存了它们的解决方案。我们只解决一次每个子问题，当我们第一次看到它时，我们已经解决了它的所有先决子问题。

这两者渐进时间复杂度一样，但是bottom-up通常有更好的常量因子，因为不同于递归它的调用负担少一些

top-down with memoization实现rod cutting的伪代码如下：

memorizedCutRod(p,n)
  let r[0...n] be a new array
  for i=0 to n 
    r[i]=-1
  return  memorizedCutRodAux(p,n,r)
memorizedCutRodAux(p,n,r)
  if r[n]>=0
    return r[n]
  if n==0
    q=0
  else q=-1
    for i=1 to n
      q=max(q,p[i]+memorizedCutRodAux(p,n-i,r))
  r[n]=q
  return q

bottom-up method实现rod cutting的伪代码如下：

bottomUpCutRod(p,n)
  let r[0...n] be a new array
  r[0]=0
  for j=1 to n 
    q=-1
      for i=1 to j
        q=max(q,p[i]+r[j-i])
      r[j]=q
  return   r[n]

使用动态规划求解的时间复杂度为 $\Theta(n^2)$

根据计算出的信息构造一个最优解

上述代码给出了最优解的值，却没有给出一个最优解，如下代码可以构造出一个最优解，它使用了一个额外的数组s[i]记录第一个切割的钢管的长度

extendedBottomUpCutRod(p,n)
  let r[0,...,n]   and s[0,...,n] be new array
  r[0]=0
  for j=1 to n
    q=-1 
    for i= 1 to j
      if q< p[i]+r[j-i]
          q=p[i]+r[j-1]
          s[j]=i
       r[j]=q
  return r and s

printCutRodSolution(p,n)
  (r,s)=extendedBottomUpCutRod(p,n)
  while n>0
    print s[n]
    n=n-s[n]

printCutRodSolution(p,7)会打印1 6 表示一种最优解