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];//保存每次計(jì)算的結(jié)果
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];//加上當(dāng)前的和
}
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;
}
說(shuō)明
對(duì)于以下函數(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];//加上當(dāng)前的和
}
相當(dāng)于遞歸調(diào)用不斷求出每一條路徑的值沛婴，并且比較大小——但是直接提交的話(huà)會(huì)超時(shí)，因?yàn)橹貜?fù)的計(jì)算太多。
如果每算出一個(gè)值就保存起來(lái)的話(huà)艺挪，那么第二次需要相同的值的時(shí)候就可以直接進(jìn)行調(diào)用撩嚼，如下所示：
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];//加上當(dāng)前的和
}
return maxSum[i][j];
}
