NYOJ 18 The Triangle

       动态规划问题，题意是输入一个数字三角形，然后从上往下走一条路，问走到底端的最大值。如果从上往下走的话会有很多种情况，所以不如反过来从下往上递推，比较大小求最大值。

AC代码：

#include <iostream>
#include <cstdio>
#define MAX(a,b) (((a)>(b))?(a):(b))
using namespace std;
int MAP[105][105];
int n;

int main()
{
	scanf("%d",&n);
	for(int i=1;i<=n;i++){
		for(int j=1;j<=i;j++){
			scanf("%d",&MAP[i][j]);
		}
	}
	for(int i=n-1;i>=1;i--){
		for(int j=1;j<=i;j++){
			MAP[i][j] = MAX(MAP[i+1][j],MAP[i+1][j+1]) + MAP[i][j];
		}
	}
	printf("%d\n",MAP[1][1]);
	return 0;
}