本文共 2811 字，大约阅读时间需要 9 分钟。
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#include #include #include #include using namespace std;#define maxn 105int 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#include #include #include #include using namespace std;#define maxn 105int 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; }
转载地址：http://zszci.baihongyu.com/