在讲述DP算法的时候,一个经典的例子就是数塔问题,它是这样形容的:
有如下所示的数塔,要求从顶层走到底层,若每一步只能走到相邻的结点,则通过的结点的数字之和最大是多少?
曾经通知你了,这是个DP的题目,你能AC吗?
Input
输出数据首先包含一个整数C,示意测试实例的个数,每个测试实例的第一行是一个整数N(1 <= N <= 100),示意数塔的高度,接下来用N行数字示意数塔,其中第i行有个i个整数,且所有的整数均在区间[0,99]内。
Output
对于每个测试实例,输入可能失去的最大和,每个实例的输入占一行。
Sample Input
1
5
7
3 8
8 1 0
2 7 4 4
4 5 2 6 5
Sample Output
30
本文用动静布局和改良的深度优先算法(记忆化搜寻)两种方法
//(dp做法,找递归式ans[i][j] = max(ans[i+1][j],ans[i+1][j+1])+自身a[i][j]) //#include<iostream>//#include<algorithm>//#include<string>//#include<string.h>//#include<cstdio>//#include<queue>//#include<stack> //#include<set>//#include<map> //#include<vector> //using namespace std;//int ans[105][105],a[105][105];//int main(){// int t = 0;// cin >> t;// while(t--){// int n = 0;// cin >> n;// memset(ans,0,sizeof(ans));// for(int i=1;i<=n;i++){// for(int j=1;j<=i;j++){// cin >> a[i][j];//输出各行数据 // }// }// for(int i=n;i>=1;i--){// for(int j=1;j<=i;j++){// ans[i][j] = max(ans[i+1][j],ans[i+1][j+1])+a[i][j];//从底层向上,计算各地位可失去的最大值再加上该地位自身的数字值 // }// }// cout << ans[1][1] << endl;//因为是自底向上,所以第一行的第一个数是所求的最大门路 // }// return 0;//}
(深搜改良做法(记忆化搜寻))//#include<iostream>//#include<algorithm>//#include<string>//#include<string.h>//#include<cstdio>//#include<queue>//#include<stack> //#include<set>//#include<map> //#include<vector> //using namespace std;//int n;//int ans[105][105],a[105][105];//a为存储点的数组,ans为所求后果数组 //int dfs(int i,int j){// if(i == n){// return ans[i][j] = a[i][j];//递归进口,i曾经搜寻到底部了 // }// if(ans[i][j]>=0){//初始值为-1,ans数>=0,示意曾经被拜访过并且已失去相应的ans值(要不ans不会>=0),则间接返回以后数字,不再往下拜访搜寻 // return ans[i][j];//没有此if语句就是失常的dfs,加上这一步(记忆化搜寻)能够升高工夫复杂度2^n到n^2,防止反复拜访和计算各点的ans // }// return ans[i][j] = max(dfs(i+1,j),dfs(i+1,j+1)) + a[i][j]; //}//int main(){// int t = 0;// cin >> t;// while(t--){// cin >> n;// memset(ans,-1,sizeof(ans));// for(int i=1;i<=n;i++){// for(int j=1;j<=i;j++){// cin >> a[i][j];//输出各行数据 // }// }// cout << dfs(1,1) << endl;//从终点开始dfs // }// return 0;//}