POJ 1163 The Triangle

The Triangle Time Limit: 1000MS Memory Limit: 10000KTotal Submissions: 48894 Accepted: 29544

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. 

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题目，虽然还是有看题解的成分才容易得做出来。。。。。。感觉自己真的好弱，不过还好没有失去信心！这道题目使用在未了解DP（动态规划）之前会很费劲，程序很容易因为大量的回溯产生递归调用或者循环而TL或者RE，当知道了一点DP的思想之后会发现这就是典型的简单DP题目。

因为它要求按照图中非负整数组成的三角形从第一行开始，每次可以往左下或者右下走一格，直到走到最下行，把沿途经过的数全部加起来。问如何走才可以使得这个和尽可能的最大？

将当前位置（i，j）看作状态d(i,j)，那么利用抽象思维，可以得到一个与当前状态有关的状态方程：

d(i,j)=a(i,j)+max(d(i+1,j),d(i+1,j+1));

为了方便计算，可以从倒数第二层开始逐层往上进行循环，这样就可以将倒数第一层的最大值加到倒数第二层，再选择较大的加到倒数第三层。

代码如下。

#include <iostream> #include <cstdio> #include <algorithm> using namespace std; int a[100][100]; int n; int main(int argc, char const *argv[]) { scanf("%d",&n); for(int i=0;i<n;i++) for(int j=0;j<=i;j++) scanf("%d",&a[i][j]); for(int i=n-2;i>=0;i--) for(int j=0;j<=i;j++) a[i][j]+=max(a[i+1][j],a[i+1][j+1]); printf("%d\n",a[0][0]); return 0; }