递归和动态规划.ppt

递归和动态规划
内容提要
递归:
(1)将原问题分解为更小规模的同类问题
(2)结束条件
#include ""
int factorial(int n)
{
if(n<=0)return(-1);
if(n==1) return(1);
else return n*factorial(n-1);
}
int main(int argc, char* argv[])
{
printf("%d\n",factorial(5));
getchar();
return 0;
}
f(5)
f(4)
f(3)
f(2)
f(1)
线性的
f(x)->g(f(x-x’))
每个f(x-x’)只计算一次。
树形递归
例8:POJ 2753 i数列
1,1,…,f(n-1)+f(n-2),…
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
冗余计算
例8:POJ 2753 i数列
计算过程中存在冗余计算,为了出去冗余计算
可以从已知条件开始计算,并记录计算过程中
的中间结果。
f(1)
1
动态规划
例8:POJ 2753 i数列
int f[n+1];
f[1]=f[2]=1;
int I;
for(i=3;i<=n;i++)
f[i] = f[i-1]+f[i-2];
cout << f[n] <<endl;
动态规划的实质
动态规划的实质就是
就是将用递归解决时会重复计算的值,算好一次后就存起来,以后不必重新计算,用空间换时间。动态规划通常用求最优解,能用动态规划解决的求最优解问题,必须满足最优解的每个局部也都是最优的。
记忆化搜索
动态规划
例9 POJ 1163 数字三角形
在上面的数字三角形中寻找一条从顶部到底边的路径,使得路径上所经过的数字之和最大。路径上的每一步都只能往左下或右下走。只需要求出这个最大和即可,不必给出具体路径。
三角形的行数大于1小于等于100
数字为0 - 99
7
3 8
8 1 0
2 7 4 4
4 5 2 6 5
输入格式:
//三角形行数。下面是三角形
7
3 8
8 1 0
2 7 4 4
4 5 2 6 5
要求输出最大和
算法一:递归的想法
设f(i,j) 为三角形上从点(i,j)出发向下走的最长路经,则
f(i,j) = max(f(i+1,j), f(i+1,j+1))+d[i][j]
要输出的就是f(1,1,)即从最上面一点出发的最长路经。
代码如下: