(动态规划经典问题.docxVIP

动态规划经典问题1、三角数塔问题设有一个三角形的数塔，顶点为根结点，每个结点有一个整数值。从顶点出发，可以向左走或向右走，如图所示： 要求从根结点开始，请找出一条路径，使路径之和最大，只要输出路径的和。【代码】////例题1 三角数字塔问题 ////#include stdio.h#include stdlib.h#define MAXN 101int n,d[MAXN][MAXN];int a[MAXN][MAXN];void fnRecursive(int,int);//递推方法函数声明int fnMemorySearch(int,int);//记忆化搜索函数声明int main(){ int i,j; printf(输入三角形的行数n(n=1-100):\n); scanf(%d,n); printf(按行输入数字三角形上的数(1-100):\n); for(i=1; i=n; i++) for(j=1; j=i; j++) scanf(%d,a[i][j]); for(i=1; i=n; i++) for(j=1; j=i; j++) d[i][j]=-1;//初始化指标数组 printf(递推方法：1\n记忆化搜索方法：2\n); int select; scanf(%d,select); if(select==1) { fnRecursive(i,j);//调用递推方法 printf(\n%d\n,d[1][1]); } if(select==2) { printf(\n%d\n,fnMemorySearch(1,1));//调用记忆化搜索方法 } else printf(输入错误！); return 0;}void fnRecursive(int i,int 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]+(d[i+1][j]d[i+1][j+1]?d[i+1][j]:d[i+1][j+1]);}int fnMemorySearch(int i,int j)//记忆化搜索实现过程{ if(d[i][j]=0) return d[i][j]; if(i==n) return(d[i][j]=a[i][j]); if(fnMemorySearch(i+1,j)fnMemorySearch(i+1,j+1)) return(d[i][j]=(a[i][j]+fnMemorySearch(i+1,j))); else return(d[i][j]=(a[i][j]+fnMemorySearch(i+1,j+1)));}2、硬币问题问题描述：有n种硬币，面值分别为V1,V2,…,Vn, 每种有无限多。给定非负整数S，可以选用多少硬币，使得面值之和恰好为S，输出硬币数目的最小值和最大值。（1=n=100,0=S=10000,1=Vi=S）【代码】////例题1 硬币问题 ////#include stdio.h#include stdlib.h#define INF 100000000#define MAXNUM 10000#define MONEYKIND 100int n,S;int V[MONEYKIND];int min[MAXNUM],max[MAXNUM];void dp(int*,int*);//递推方法函数声明void print_ans(int*,int);//输出函数声明int main(){ int i; printf(输入硬币的种数n(1-100):\n); scanf(%d,n); printf(输入要组合的钱数S(0-10000):\n); scanf(%d,S); printf(输入硬币种类：\n); for(i=1; i=n; i++) { scanf(%d,V[i]); } dp(min,max); printf(最小组合方案：\n); print_ans(min,S); printf(\n); printf(最大组合方案：\n); print_ans(max,S); return 0;}void dp(int *min,int *max)//递推过程实现{ int i,j; min[0] = max[0] = 0; for(i=1; i=S; i++)//初始化数组 { min[i]=INF; max[i]=-INF; } for(i=1; i=S; i++) for(j=1; j=n; j++) if(i=V[j]) { if(min[i-V[j]]+1min[i]){ min[i]=min[i-V[j]]+1;//最小组合过