在讲述 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;
//}