数字三角形问题

5
7
3 8
8 1 0 
2 7 4 4
4 5 2 6 5

30

解题思路：
    将原题数据如下编码：
    7（1，1）    
    3（2，1） 8（2，2）
    8（3，1） 1（3，2） 0（3，3） 
    2（4，1） 7（4，2） 4（4，3） 4（4，4）
    4（5，1） 5（5，2） 2（5，3） 6（5，4） 5（5，5）

    1、把当前（i，j）看成一个状态
    2、定义状态的指标函数dp（i，j）为从（i，j)出发时能得到的最大和（包括dp（i，j）本身的值）。
       （1）从（i，j）出发有2种决策，即向左，向右，如果向左走，需要先知道（i+1，j）出发后的最大和，即dp（i+1，j），如果向右走，需要先知道（i+1，j+1）出发后的最
       大和，状态转移方程为：dp（i，j）=dp（i，j）+max（dp（i+1，j），dp（i+1，j+1））
       （2）原问题即可抽象为填下面格子的问题 （绿色为已知数，依次填充与其平行的每一行）
                                       （5，5）

                               （5，4）（4，4）

                       （5，3）（4，3）（3，3）
               （5，2）（4，2）（3，2）（2，2）
       （5，1）（4，1）（3，1）（2，1）（1，1）

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std; 

int dp[105][105];

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