1.題目信息（http://poj.org/problem?id=1163）
The Triangle
| Time Limit:?1000MS | ? | Memory Limit:?10000K |
| Total Submissions:?30397 | ? | Accepted:?17973 |
Description
7 3 8 8 1 0 2 7 4 4 4 5 2 6 5(Figure 1)
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
1.記憶遞歸型動歸
#include <iostream>
#include <algorithm>
#define m 101
using namespace std;
int n;
int d[m][m];
int maxsum[m][m];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(i=1;i<=n;i++)for(j=1;j<=i;j++){cin>>d[i][j];maxsum[i][j]=-1;}cout<<MAXsum(1,1)<<endl;return 0;
}
#include <iostream>
#include <algorithm>
using namespace std;int main()
{int n;int d[101][101];int maxsun[101][101];cin>>n;for(int i=0;i<n;i++)for(int j=0;j<=i;j++){cin>>d[i][j];}for(int i=0;i<n;i++){maxsun[n-1][i]=d[n-1][i];//cout<<d[n-1][i];}for(int i=n-2;i>=0;i--)for(int j=0;j<=i;j++)maxsun[i][j]=max(maxsun[i+1][j],maxsun[i+1][j+1])+d[i][j];cout<<maxsun[0][0]<<endl;/*for(int i=0;i<n;i++){for(int j=0;j<=i;j++){cout<<maxsun[i][j];}cout<<""<<endl;}*/return 0;
}3.空間優化
#include <iostream>
#include <algorithm>
using namespace std;
#define m 101
int d[m][m];
int n;
int *maxsum;
int main()
{int i,j;cin>>n;for(i=1;i<=n;i++)for(j=1;j<=i;j++)cin>>d[i][j];maxsum =d[n];for(i=n-1;i>=1;i--)for(j=1;j<=i;j++)maxsum[j]=max(maxsum[j],maxsum[j+1])+d[i][j];cout<<maxsum[1]<<endl;return 0;
}
)
)
