动态规划入门01

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;
}

---

说明

对于以下函数：

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];
}