程序设计-动态规划.ppt

程序设计实习
第八讲
动态规划
例1:POJ 2753 i数列
求 i数列的第n项
int f (int n){
if(n==0 || n==1){
return n;
}
return f(n-1)+f(n-2);
}
树形递归存在冗余计算
f(5)
f(3)
f(2)
f(1)
f(2)
f(4)
f(0)
f(1)
f(0)
f(3)
f(2)
f(1)
f(1)
f(0)
f(1)
1
1
0
0
1
0
1
0
如何去除冗余——动态规划
int f[n+1];
f[1] = f[2] = 1;
for(int i = 3; i <= n; i++)
f[i] = f[i-1] + f[i-2];
cout << f[n] <<endl;
为了除去冗余计算,可以从已知条件开始计算,并记录计算过程中的中间结果。
例2 POJ1163 数字三角形
在右面的数字三角形中寻找一条从顶部到底边的路径,使得路径上所经过的数字之和最大。
路径上的每一步都只能往左下或右下走。只需要求出这个最大和即可,不必给出具体路径。
三角形的行数大于1小于等于100,数字为 0 – 99。
7
3 8
8 1 0
2 7 4 4
4 5 2 6 5
输入格式:第一行是三角形行数,下面是三角形。
5
7
38
8 1 0
2 7 4 4
4 5 2 6 5
输出:要求输出最大和。
解题思路
D(r, j):表示第r行第 j 个数字;
MaxSum(r, j):表示从D(r, j)到底边的各条路径中,数字之和最大的那条路径的数字之和;
本题目标是求: MaxSum(0,0)。
从某个D(r, j)出发,下一步只能走D(r+1,j)或者
D(r+1, j+1)。所以,对于N行的三角形,可以得到递推公式:
if ( r == N-1 )
MaxSum(r, j) = D(N-1, j);
else
MaxSum( r, j) = Max{ MaxSum(r+1, j), MaxSum(r+1, j+1) } + D(r, j);
#include <>
#define MAX 101
int triangle[MAX][MAX];
int n;
int longestPath(int i, int j);
void main(){
int i, j;
cin >> n;
for(i = 0; i < n; i++)
for(j = 0; j <= i; j++)
cin >> triangle[i][j];
cout << longestPath(0,0) << endl;
}
数字三角形的递归程序
int longestPath(int i, int j){
if(i == n)
return 0;
int x = longestPath(i + 1, j);
int y = longestPath(i + 1, j + 1); if(x < y)
x = y; return x + triangle[i][j];
}
超时!!
数字三角形的递归程序
为什么超时?
因为重复计算太多!
7
3 8
8 1 0
2 7 4 4
4 5 2 6 5
如果采用递规的方法,深度遍历每条路径,存在大量重复计算。则时间复杂度为 2^n,对于 n = 100,肯定超时。