数塔
Problem Description
在讲述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
题意：
输入n层塔，第n层就有n个数，然后要求求出从顶层走到底层能够得到的最大的数。
这个题目可以有两种解决方法：
第一种：从底层向顶层推。
在样例中，从第5层走向第4层，第4层中的
第一个元素2可以+4，也可以+5，我们就要选择相加之和最大的2+5=7；
第二个元素7可以+5，也可以+2，我们选择相加之和最大的7+5=12；
第三个元素4可以+2，也可以+6，我们选择相加之和最大的4+6=10；
第四个元素4可以+6，也可以+5，我们选择相加之和最大的4+6=10；
从第4层再走向第3层，第3层中的
第一个元素8可以+7，也可以+12，我们选择相加之和最大的8+12=20；
第二个元素1可以+12，也可以+10，我们选择相加之和最大的1+12=13；
第三个元素0可以+10，也可以+10，两值相等所以相加之和为0+10=10；
从第3层走向第2层，第2层中的
第一个元素3可以+20，也可以+13，我们选择相加之和最大的3+20=23；
第二个元素8可以+13，也可以+10，我们选择相加之和最大的8+13=21；
从第2层走向第1层，第1层中的
第一个元素7可以+23，也可以+21，我们选择相加之和最大的30；
所以最大值为30。
第二种：从顶层向底层推。
从第1层走到第2层，第2层中的
第一个元素3+7=10；
第二个元素8+7=15；
从第2层走向第3层，第3层中的
第一个元素8+10=18；
第二个元素1可以+10，也可以+15，我们选择相加之和最大的1+15=16；
第三个元素0+15=15；
从第3层走向第4层，第4层中的
第一个元素2+18=20；
第二个元素7可以+18，也可以+16，我们选择相加之和最大的7+18=25；
第三个元素4可以+16，也可以+15，我们选择相加之和最大的4+16=20；
第四个元素4+15=19；
从第4层走向第5层，第5层中的
第一个元素4+20=24；
第二个元素5可以+20，也可以+25，我们选择相加之和最大的5+25=30；
第三个元素2可以+25，也可以+20，我们选择相加之和最大的2+25=27；
第四个元素6可以+20，也可以+19，我们选择相加之和最大的6+20=26；
第五个元素5+19=24；
所以遍历第五层我们可以找到最大值为30。
第一种方法：从底层向顶层推：
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
using namespace std;
#define maxn 105
int dp[maxn][maxn],num[maxn][maxn];
int main()
{int n,c;scanf("%d",&c);while(c--){scanf("%d",&n);memset(dp,0,sizeof(dp));for(int i=1;i<=n;i++){for(int j=1;j<=i;j++)scanf("%d",&num[i][j]);} for(int i=1;i<=n;i++)dp[n][i]=num[n][i];for(int i=n-1;i>=1;i--){for(int j=1;j<=i;j++){dp[i][j]=max(dp[i][j],num[i][j]+dp[i+1][j]);dp[i][j]=max(dp[i][j],num[i][j]+dp[i+1][j+1]);}}printf("%d\n",dp[1][1]);}return 0;}
第二种方法：从顶层向底层推：
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
using namespace std;
#define maxn 105
int dp[maxn][maxn],num[maxn][maxn];
int main()
{int n,c;scanf("%d",&c);while(c--){scanf("%d",&n);memset(dp,0,sizeof(dp));for(int i=1;i<=n;i++){for(int j=1;j<=i;j++)scanf("%d",&num[i][j]);}dp[1][1]=num[1][1];for(int i=2;i<=n;i++){for(int j=1;j<=i;j++){if(j==1){dp[i][j]=max(dp[i][j],num[i][j]+dp[i-1][j]);}else if(j==i){dp[i][j]=max(dp[i][j],num[i][j]+dp[i-1][j-1]);}else{dp[i][j]=max(dp[i][j],num[i][j]+dp[i-1][j]);dp[i][j]=max(dp[i][j],num[i][j]+dp[i-1][j-1]);}}}int ans=0;for(int i=1;i<=n;i++)ans=max(ans,dp[n][i]); //找到最底层的最大值printf("%d\n",ans);}return 0;}