动态规划初步.docx

第9章动态规划初步
学****目标
理解状态和状态转移方程
理解最优子结构和重叠子问题
熟练运用递推法和记忆化搜索求解数字三角形问题
熟悉DAG上动态规划的常见思路、两种状态定义方法和刷表法
掌握记忆化搜索在实现方面的注意事项
掌握1
作为“批量赋值”的参数。
),但为什么可以这样计算呢？原因在于：i是逆序枚举的,
因此在计算d[i][j]前，它所需要的d[i+1][j]和d[i+1][j+1] 一定已经计算出来了。
提示9-3 :可以用递推法计算状态转移方程。 递推的关键是边界和计算顺序。 在多数情况下， 递推法的时间复杂度是：状态总数x每个状态的决策个数x决策时间。如果不同状态的决策 个数不同，需具体问题具体分析。
方法3：记忆化搜索。程序分成两部分。首先用" memset(d, - 1,sizeof(d));”把d全部初 始化为-1,然后编写递归函数1：
int solve(int i, int j){
if(d[i][j] >= 0) return d[i][j];
return d[i][j] = a[i][j] + (i == n ? 0 : max(solve(i+1,j),solve(i+1,j+1)));
}
上述程序依然是递归的， 但同时也把计算结果保存在数组 d中。题目中说各个数都是非
负的，因此如果已经计算过某个 d[i][j],则它应是非负的。 这样，只需把所有d初始化为-1,
即可通过判断是否 d[i][j] >0得知它是否已经被计算过。
图9-3记忆化搜索
最后，千万不要忘记在计算之后把它保存在 d[i][j]中。根据C语言“赋值语句本身有返回值” 的规定，可以把保存d[i][j]的工作合并到函数的返 回语句中。
上述程序的方法称为记忆化 (memoization ),
它虽然不像递推法那样显式地指明了计算顺序， 但仍然可以保证每个结点只访问一次，如图 9-3
所示。
由于i和j都在1〜n之间，所有不相同的结点 一共只有O(n2)个。无论以怎样的顺序访问，时间 复杂度均为O(n2)。从2n〜n2是一个巨大的优化， 这正是利用了数字三角形具有大量重叠子问题的特点。
提示9-4:可以用记忆化搜索的方法计算状态转移方程。当采用记忆化搜索时，不必事先确 定各状态的计算顺序，但需要记录每个状态“是否已经计算过”
DAG上的动态规划
有向无环图上的动态规划是学****动态规划的基础。很多问题都可以转化为 DAG上的最
长路、最短路或路径计数问题。
DAG 模型
嵌套矩形问题。 有n个矩形，每个矩形可以用两个整数 a、b描述，表示它的长和宽。
矩形X(a,b)可以嵌套在矩形 Y(g d)中，当且仅当a<c, b<d,或者b<c, a<d (相当于把矩形 X 旋转90° )。例如，
(1,5)可以嵌套在(6, 2)内，但不能嵌套在(3, 4)内。你的任务是选出尽量多 的矩形排成一行，使得除了最后一个之外，每一个矩形都可以嵌套在下一个矩形内。 如果有
多解，矩形编号的字典序应尽量小。
【分析】
矩形之间的“可嵌套”关系是一个典型的二元关系，二元关系可以用图来建模。如果矩
形X可以嵌套在矩形 Y里，就从X到Y连一条有向边。这个有向图是无环的， 因为一个矩形
无法直接或间接地嵌套在自己内部。换句话说，它是一个 DAG。这样，所要求的便是 DAG
上的最长路径。
硬币问题。有n种硬币，面值分别为 Vi, V2,…，Vn,每种都有无限多。给定非负整数 S, 可以选用多少个硬币，使得面值之和恰好为 S?输出硬币数目的最小值和最大值。 1wnw
100, 0<S< 10000, 1<Vi<So
【分析】
此问题尽管看上去和嵌套矩形问题很不一样，但本题的本质也是 DAG上的路径问题。
将每种面值看作一个点，表示“还需要凑足的面值” ，则初始状态为S,目标X^态为0。若当
前在状态i,每使用一个硬币j,状态便转移到i-Vj。
这个模型和上一题类似， 但也有一些明显的不同之处： 上题并没有确定路径的起点和终
点(可以把任意矩形放在第一个和最后一个) ，而本题的起点必须为 S,终点必'须为0;点固
定之后“最短路”才是有意义的。在上题中，最短序列显然是空(如果不允许空，就是单个 矩形，不管怎样都是平凡的)，而本题的最短路却不容易确定。
最长路及其字典序
首先思考“嵌套矩形”。如何求DAG中不固定起点的最长路径呢？仿照数字三角形的做 法，设d(i)表示从结点i出发的最长路长度，应该如何写状态转移方程呢？第一步只能走到 它的相邻点，因此：
d(i)=max{d(j) 1| (i, j) E}
其中，E为边集。最终答案是所有 d(i)中的最大值。根