数字三角形问题

刘开心_1266679

发布于 2019-02-14 07:34:41

82300

代码可运行

文章被收录于专栏：开心的学习之路开心的学习之路

运行总次数：0

代码可运行

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

Sample Output

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）

3、原问题的解即为dp（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;
}