数字三角形问题 NOJ 1226

数字三角形问题

时间限制(普通/Java) : 1000 MS/ 3000 MS 运行内存限制 : 65536 KByte
总提交 : 148 测试通过 : 94

题目描述

给定一个由n行数字组成的数字三角形如下图所示。试设计一个算法，计算出从三角形的顶至底的一条路径，使该路径经过的数字总和最大。

对于给定的由n行数字组成的数字三角形，编程计算从三角形的顶至底的路径经过的数字和的最大值。

输入

输入的第1行是数字三角形的行数n，1≤n≤100。接下来n行是数字三角形各行中的数字。所有数字在0..99之间。

输出

输出到的第1行中的数是计算出的最大值。

样例输入

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

样例输出

分析：采用记忆化搜索，程序分成两部分，首先用memset(b,-1,sizeof(b));把b的值全部初始化为-1。然后编写递归函数。

实现代码：

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<math.h>
#include<iostream>
#include<algorithm>
using namespace std;
int n,i,j;
int a[101][101],b[101][101];
int solve(int i,int j)
{
    if(b[i][j]>=0) return b[i][j];
    return b[i][j]=a[i][j]+(i==n?0:max(solve(i+1,j),solve(i+1,j+1)));
}
int main()
{
    scanf("%d",&n);
    memset(a,0,sizeof(a));
    memset(b,-1,sizeof(b));
    for(i=0;i<n;i++)
    {
        for(j=0;j<=i;j++)
        {
            scanf("%d",&a[i][j]);
        }
    }
    printf("%d
",solve(0,0));
}