动态规划初步.doc

第 9 章动态规划初步
学****目标
理解状态和状态转移方程
理解最优子结构和重叠子问题
熟练运用递推法和记忆化搜索求解数字三角形问题
熟悉 DAG 上动态规划的常见思路、两种状态定义方法和刷表调用关系树。看到了吗？
solve(3, 2)被
2,1
2,2
计算了两次（一次是 solve(2, 1)需要的，
一次是 solve(2, 2)需要的）。也许读者会
3,1
3,2
3,2
3,3
认为重复算一两个数没有太大影响，但
事实是：这样的重复不是单个结点，而
4,1
4,2
4,2
4,3
4,2
4,3
4,3
4,4
是一棵子树。 如果原来的三角形有 n 层，
图 9-2
则调用关系树也会有 n 层，一共有 2n- 1
重叠子问题
个结点。
提示 9-2 ：用直接递归的方法计算状态转移方程，效率往往十分低下。其原因是相同的子问
题被重复计算了多次。
方法 2：递推计算。程序如下（需再次注意边界处理） ：
int i, j;
for(j = 1; j <= n; j++) d[n][j] = a[n][j];
for(i = n-1; i >= 1; i--)
for(j = 1; j <= i; j++)
d[i][j] = a[i][j] + max(d[i+1][j],d[i+1][j+1]);
程序的时间复杂度显然是
O(n2)，但为什么可以这样计算呢？原因在于：
i 是逆序 枚举的，
因此在计算 d[i][j] 前，它所需要的 d[i+1][j] 和 d[i+1][j+1] 一定已经计算出来了。
提示 9-3 ：可以用递推法计算状态转移方程。
递推的关键是边界和计算顺序。
在多数情况下，
递推法的时间复杂度是：状态总数×每个状态的决策个数×决策时间。如果不同状态的决策
个数不同，需具体问题具体分析。
方法 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 得知它是否已经被计算过。
最后，千万不要忘记在计算之后把它保存在
d[i][j] 中。根据 C 语言“赋值语句本身有返回值”的规定，可以把保存 d[i][j] 的工作合并到函数的返回语句中。

1,1
2,1 2,2
上述程序的方法称为记忆化 （ memoization ），
它虽然不像递推法那样显式地指明了计算顺序，
但仍然可以保证每个结点只访问一次，如图
9-3
3,1
3,2
3,3
所示。
由于 i 和 j 都在 1~n 之间，所有不相同的结点
4,1
4,2
4,3
4,4
一共只有 O(n2)个。无论以怎样的顺序访问，
时间
图 9-3
复杂度均为 O(n2)。从 2n~n2 是一个巨大的优化，
记忆化搜索
这正是利用了数字三角形具有大量重叠子问题的特点。
提示 9-4 ：可以用记忆化搜索的方法计算状态转移方程。当采用记忆化搜索时，不必事先确
定各状态的计算顺序，但需要记录每个状态“是否已经计算过” 。
1注意这个函数的工作方式并不像它表面显示的那样 —— 如果把 - 1 改成 - 2，并不是在把所有 d 值都初始化为 - 2！请只用 0 和- 1 作为“批量赋值”的参数。
DAG 上的动态规划
有向无环图上的动态规划是学****动