题目 1177: 三角形
时间限制: 1Sec 内存限制: 128MB 提交: 3331 解决: 1396
题目描述
7
3 8
8 1 0
2 7 4 4
4 5 2 6 5
(图一)
图一表示一个5行的数字三角形。假设给定一个n行数字三角形,计算出从三角形顶至底的一条路径，使该路径经过的数字总和最大。
每一步只能由当前位置向左下或右下。
输入
你的程序要能接受标准输入。第一行包含一个整数T，表示总的测试次数。
对于每一种情况：第一行包含一个整数N,其中1 < N < 100,表示三角形的行数。
接下来的N行输入表示三角形的每一行的元素Ai,j，其中0 < Ai,j < 100。
输出
输出每次测试的最大值并且占一行。
样例输入复制
1 5 7 3 8 8 1 0 2 7 4 4 4 5 2 6 5
样例输出复制
30
递归：
#include<iostream>
using namespace std;
#define MAX 101
int a[MAX][MAX];
int n,T;
int MaxSum(int i,int j){
if(i==n)
return a[i][j];
int x=MaxSum(i+1,j);
int y=MaxSum(i+1,j+1);
return max(x,y)+a[i][j];
}
int main(){
int i,j;
cin>>t;
int k=t;
for(k=1;k<=t;k++){
cin>>n;
for(i=1;i<=n;i++)
for(j=1;j<=i;j++)
cin>>a[i][j];
cout<<MaxSum(1,1)<<endl;
}
}
return 0;
}
优化：
#include<iostream>
#include<string.h>
using namespace std;
#define MAX 101
int a[MAX][MAX];
int n,T;
int b[MAX][MAX];
int MaxSum(int i,int j){
if(b[i][j]!=-1)return b[i][j];//值不是-1，说明已经存下中间子问题的值
if(i==n)
return a[i][j];
int x=MaxSum(i+1,j);
int y=MaxSum(i+1,j+1);
b[i][j]=max(x,y)+a[i][j];
return b[i][j];
}
int main(){
int i,j,k,t;
cin>>t;
memset(b,-1,sizeof(b));
for(k=0;k<t;k++){
cin>>n;
for(i=1;i<=n;i++){
for(j=1;j<=i;j++){
cin>>D[i][j];
}
cout<<MaxSum(1,1)<<endl;
}
}
return 0;
}