题目描述
小招在玩一款游戏：在一个N层高的金字塔上，以金字塔顶为第一层，第i层有i个落点，每个落点有若干枚金币，在落点可以跳向左斜向下或向右斜向下的落点。若知道金字塔的层数N及每层的金币数量分布，请计算小招在本次游戏中可以获得的最多金币数量。
输入描述:
输入共有N + 1行(N ≤ 1024)，第一行为高度N，第二行至N + 1行 ，为该金字塔的金币数量分布。
输出描述:
输出金币数量。
示例1
输入
5
8
3 8
8 1 0
4 7 5 4
3 5 2 6 5
输出
31
#include <stdio.h>
#include <stdlib.h>
int main()
{
int n;
int i,j;
scanf("%d",&n);
int num[n][n];
int max;
int sum[n][n];
for(i=0; i<n; i++)
{
for(j=0; j<=i; j++)
scanf("%d",&num[i][j]);
}
sum[0][0]=num[0][0];
for(i=1; i<n; i++)
{
for(j=0; j<=i; j++)
if(j==0)
sum[i][j]=sum[i-1][0]+num[i][j];//数字在左腰的情况
else if(j==i)
sum[i][j]=sum[i-1][i-1]+num[i][j];//数字在右腰的情况
else//余下的普通情况
{
max=sum[i-1][j-1];
if(sum[i-1][j]>sum[i-1][j-1])
max=sum[i-1][j];
sum[i][j]=num[i][j]+max;
}
}
max=sum[n-1][0];
for(j=0; j<n; j++)
{
if(sum[n-1][j]>max)
max=sum[n-1][j];
}
printf("%d",max);
return 0;
}