http://poj.org/problem?id=1163

題目

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

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

30

代碼

#include <iostream>
#include <algorithm>
#define MAX 101
using namespace std;
int D[MAX][MAX];
int n;
int maxSum[MAX][MAX];//保存每次計算的結果
int MaxSum(int i,int j){
    if(maxSum[i][j]!=-1){
        return maxSum[i][j];
    }
    if(i==n){
        maxSum[i][j]=D[i][j];
        //走到最后一行了
    }
    else{
        int x=MaxSum(i+1,j);//往左走
        int y=MaxSum(i+1,j+1);//往右走
        maxSum[i][j]=max(x,y)+D[i][j];//加上當前的和
    }
    
    return maxSum[i][j];
}
int main(){
    int i,j;
    cin>>n;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=i;j++){
            cin>>D[i][j];
            maxSum[i][j]=-1;
        }
    }
    cout<<MaxSum(1,1)<<endl;
    return 0;
}

說明

對于以下函數(shù)：

int MaxSum(int i,int j){
    if(i==n){
        return D[i][j];
        //走到最后一行了
    }
    int x=MaxSum(i+1,j);//往左走
    int y=MaxSum(i+1,j+1);//往右走
    return max(x,y)+D[i][j];//加上當前的和
}

相當于遞歸調用不斷求出每一條路徑的值，并且比較大小——但是直接提交的話會超時，因為重復的計算太多。
如果每算出一個值就保存起來的話，那么第二次需要相同的值的時候就可以直接進行調用，如下所示：

int MaxSum(int i,int j){
    if(maxSum[i][j]!=-1){
        return maxSum[i][j];
    }
    if(i==n){
        maxSum[i][j]=D[i][j];
        //走到最后一行了
    }
    else{
        int x=MaxSum(i+1,j);//往左走
        int y=MaxSum(i+1,j+1);//往右走
        maxSum[i][j]=max(x,y)+D[i][j];//加上當前的和
    }
    
    return maxSum[i][j];
}