數字三角形問題 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

樣例輸出

30

分析：采用記憶化搜尋，程式分成兩部分，首先用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\n",solve(0,0));
}