Description 在讲述DP算法的时候，一个经典的例子就是数塔问题，它是这样描述的：
有如下所示的数塔，要求从顶层走到底层，若每一步只能走到相邻的结点，则经过的结点的数字之和最大是多少？
已经告诉你了，这是个DP的题目，你能AC吗? Input 输入数据首先包括一个整数C,表示测试实例的个数，每个测试实例的第一行是一个整数N(1 <= N <= 100)，表示数塔的高度，接下来用N行数字表示数塔，其中第i行有个i个整数，且所有的整数均在区间0,990,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）解决。 动态规划和贪心算法不同，贪心算法通过找到每一个状态最优解的情况从而找到整个问题最优解。而有些问题当前的最优解并不能代表最后的最优解，他们最优解的情况会不断变化。这时就需要采用动态规划思想，不停地跟新当前的最优状态，直到最后达到最优解。 解决动态规划的问题关键便是如何正确的转移当前的状态到下一个状态，也可以理解为将大问题不断的转化为小问题解决。 比如这个问题，我们可以通过将第最后一层的叶子结点加到他的父亲节点上，每个父亲节点有两个孩子节点，取最大值。这样第最后一层的节点就不需要再考虑了。这个时候整个需要考虑的树减少了一层。以此类推直到根节点即为最终答案。 代码实现
#include<iostream>#include<cstdio>#include<algorithm>using namespace std;int array[101][101];int main(){ int C; scanf("%d",&C); while(C--){ int N; scanf("%d",&N); for(int i=0;i<N;i++) for(int j=0;j<i+1;j++) scanf("%d",&array[i][j]); for(int i=N-2;i>=0;i--) for(int j=0;j<i+1;j++) array[i][j]+=max(array[i+1][j],array[i+1][j+1]); cout<<array[0][0]<<endl; } return 0;}新闻热点
疑难解答
