[数据结构和算法]《算法导论》动态规划笔记(1)

动态规划是求解最优化问题的方法，这类问题有很多可行解，每个解都有一个值，我们希望寻找具有最优值的解。我们称这个解为问题的一个最优解，而不是最优解，因为可能有多个解都达到最优值。

钢条切割问题

Serling公司购买长钢条，将其切割为短钢条出售。不同长度i的价格如下表：

问题描述为：给定一段长度为n英寸的钢条和一个价格表pi，求切钢条方案，使得销售收益最大。

课本上举了一个当n=4英寸的栗子，n=4时，有8种切割方案，其中切为两段2英寸的方案，收益最大为10.

最优子结构

为了求解规模为n的原问题，我们先求解形式完全一样，但规模更小的两个子问题，即当首次切割后，我们将两段钢条看成独立的钢条切割问题。我们通过组合两个相关子问题的最优解，并在所有可能的两段切割方案中选取组合收益最大者，构成原问题的最优解。我们称钢条切割问题满足 最优子结构性质：问题的最优解由相关子问题的最优解组合而成，而这些子问题可以独立求解。

自顶向上递归实现

除了上面说的方法，还有一种求解方法。利用递归的思想，首先将钢条从左边切割下长度为i的一段，只对右边剩下的长度为n-i的一段继续进行切割，对左边切割过的一段不再切割。问题分解的方式为：将长度为n的钢条分解为左边开始一段，以及剩余部分继续分解的结果。这样，不做任何切割的方案就可以描述为：第一段长度为n，收益为pn，剩余长度部分为0.对应的收益为0.

伪代码如下：

CUT-ROD(p,n)
# 如果n=0，则直接返回0
if n == 0
    return 0

q = 负无穷
for i =1 to n
    # 对于i从1到n，循环计算第i段和剩下n-i段的最大收益

    q = max(q, p[i] + CUT-ROD(p, n-i))

return q

CUT-ROD的输入是价格数组p[1..n]和整数n，输出是最大收益。

CUT-ROD过程是非常耗时的，原因在于其反复用相同参数值对自身进行递归调用，即他反复求解相同子问题。时间为n的指数函数，T（n）=2^n

使用动态规划求解

刚才看到用递归的方法求解太费时间了，然后看看用动态规划怎么求解。动态规划对每个子问题只求解一次，并将结果保存下来。如果随后再次需要此字问题的解，只需要查找保存的结果，而不必重新计算。注意这里要保存之前的计算结果，所以会消耗一定的存储空间，所以动态规划是典型的时空权衡的例子。

动态规划有2中等价求解方法，先看第一种

1. 带备忘的自顶向下法

此方法扔按照自然的递归形式编写过程，但过程会保存每个子问题的解，通常保存在一个数组或者散列表中，（散列表后面再说）当需要一个子问题的解时，过程首先检查是否已经保存过此解。如果是，则直接返回保存的值，从而节省了计算时间。否则，按通常方式计算这个子问题，我们称这个递归过程是带备忘的，因为他“记住了”之前已经计算过的结果。

2.自底向上法

刚才是自顶向下，现在刚好相反，是自底向上。通俗理解一下，自底向上就是先把原问题分解为规模大小按顺序排列的子问题，使得每个子问题的解只依赖规模更小的子问题的解，然后按规模大小排序，那么当求解某个子问题时，他所依赖的更小的子问题的解已经保存了，那么每个子问题也就只需要求解一次。

下面是带备忘的自顶向上的CUT-ROD过程的伪代码

# 主过程
MEMOIZED-CUT-ROD（p，n）
let r[0..n] be a new array
for i=0 to n
        # 令新建数组r的值都为负无穷，
        # 然后调用辅助过程MEMOIZED-CUT-ROD-AUX
        r[i] = 负无穷

return MEMOIZED-CUT-ROD-AUX(p,n,r)
MEMOIZED-CUT-ROD-AUX(p,n,r)
if r[n] >=0
        return r[n]

# 如果长度为0，则直接返回0.
if n ==0
        q = 0

# 和前面的CUT-ROD方法一样
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）
# 新建数组r，保存子问题的解
let r[0..n] be a new array
# 如果长度为0， 则解为0.
r[0]=0
# 对j由升序方式求解每个规模为j的子问题，求解规模为j的子问题方法
# 和CUT- ROD所采用的方法相同，只是现在直接访问数组元素r[j-i] 来
# 获得规模为j-i的子问题的解，避免重复求解带来的时间消耗。
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]

这一章内容挺多的，先介绍到这里了，下次继续。