文档介绍：第四讲动态规划
问题
一个楼梯有20级,每次走1级或2级,从底走到顶一共有多少种走法?
分析
假设从底走到第n级的走法有f(n)种,走到第n级有两个方法
一个是从第n-1级走1步,另一个是从第n-2级走2步,前者有f(n—1)种方法,后者有f(n-2)种方法
所以f(n)=f(n-1)+f(n-2)
易知f(0)=1,f(1)=1
int f(int n) {
if(n==0 || n==1) return 1;
return f(n-1) + f(n-2);
}
void main() {
cout<<f(20)<<endl;
}
分析
可递归求解
子问题有重叠
解决方法
每个子问题及其解记录下来,只求解一次
int dp[100]; //用于保存f(n)的结果
int f(int n) {
if(dp[n]) return dp[n]; //如果问题已经被求解,则直接返回结果
int result;
if(n==0 || n==1) result=1;
else result = f(n-1) + f(n-2);
return dp[n] = result; //记录问题的解,并返回
} void main() {
memset(dp, 0, sizeof(dp)); //初始化结果集
cout<<dp(20)<<endl;
}
引言——由一个问题引出的算法
如图,各结点代表城市,两结点间连线上数字表示城市间的距离。试找出从结点A到结点E的最短距离
A
B1
B2
C1
C2
C3
C4
D1
D2
D3
E
6
2
8
11
12
8
7
6
9
11
12
7
5
15
10
6
4
17
12
深度优先搜索法来解决此问题,该问题的递归式为
其中是(v)与v相邻的节点的集合,w(v,u)表示从v到u的边的长度
算法如下:
int MinDistance(v)
{
if ( v == E )
return 0;
else {
min = maxint;
for ( 所有没有访问过的节点i ) {
if ( v和i相邻) {
标记i访问过了;
t = v到i的距离+MinDistance(i);
标记i未访问过;
if ( t<min ) min=t;
}
return min;
}
}
MinDistance(A)就是从A到E的最短距离
算法分析
除了已经访问过的城市外,其他城市都要访问,所以时间复杂度为O(n!)
观察一下这个算法:
求B1到E的最短距离时,先求C3到E的最短距离
求B2到E的最短距离时,C3到E有求了一次
同样可知,D1到E的最短距离被求了四遍
如果求解过程中,将求得的最短距离"记录在案",随时调用,就可以避免这种情况
改进算法
进一步,改递归为递推,减少递归调用开销
如图可知,A只和Bi相邻,Bi只和Ci相邻,...,原问题的解决过程划分为4个阶段,设S1={A}, S2={B1,B2},S3={C1,C2,C3,C4},S4={D1,D2,D3},Fk(u)表示从Sk中的点u到E的最短距离
F1(A)就是从A到E的最短距离,T(n)=O(n)