Description
7 3 8 8 1 0 2 7 4 4 4 5 2 6 5 (Figure 1)
Figure 1 shows a number triangle. Write a program that calculates the highest sum of numbers passed on a route that starts at the top and ends somewhere on the base. Each step can go either diagonally down to the left or diagonally down to the right.
Input
Your program is to read from standard input. The first line contains one integer N: the number of rows in the triangle. The following N lines describe the data of the triangle. The number of rows in the triangle is > 1 but <= 100.
The numbers in the triangle, all integers, are between 0 and 99.
The numbers in the triangle, all integers, are between 0 and 99.
Output
Your program is to write to standard output. The highest sum is written as an integer.
Sample Input
5 7 3 8 8 1 0 2 7 4 4 4 5 2 6 5
Sample Output
30
这题思路和dp file *1差不多，逐渐看得出动态规划所说的把大问题化为小问题的思想了。假设dp[i][j]就是（i,j）为终点的最大sum值，他就是要么从（i-1,j）来，要么从（i-1,j-1)来，所以dp[i][j]=max{dp[i-1][j],dp[i-1][j-1]}+data[i][j];假设是从（i-1,j)来，那么问题不就变成以（i-1,j)为终点的问题么，顺利把大问题化成了小问题。实现过程中只涉及到本身前面的点dp值，所以可以从开始一个一个往后推，做法比起dp file *1简单，同时这就是传闻中的数塔了。
贴代码：
#include<iostream> using namespace std; int data[101][101],dp[101][101]; int main() { int i,j,max,row,ans; cin>>row; for(i=1;i<=row;i++) { for(j=1;j<=i;j++) cin>>data[i][j]; } ans=dp[1][1]=data[1][1]; for(i=2;i<=row;i++) { for(j=1;j<=i;j++) { max=dp[i-1][j]>dp[i-1][j-1]?dp[i-1][j]:dp[i-1][j-1]; dp[i][j]=max+data[i][j]; if(dp[i][j]>ans) ans=dp[i][j]; } } cout<<ans<<endl;
}