Problem 1004 Number Triangle
Accept: 2230 Submit: 5895Time Limit: 1000 mSec Memory Limit : 32768 KB
Problem Description
Consider the number triangle shown below. Write a program that calculates the highest sum of numbers that can be 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.
7 3 8 8 1 0 2 7 4 4 4 5 2 6 5 |
In the sample above, the route from 7 to 3 to 8 to 7 to 5 produces the highest sum: 30.
Input
There are multiple test cases.The first line of each test case contains R (1 <= R <= 1000), the number of rows. Each subsequent line contains the integers for that particular row of the triangle. All the supplied integers are non-negative and no larger than 100.
Output
Print a single line containing the largest sum using the traversal specified for each test case.
Sample Input
5
7
3 8
8 1 0
2 7 4 4
4 5 2 6 5
Sample Output
30
很明显的一道动归题,类似于求最大路径,方法有很多,搜索啊,递归啊,,,但用动归是最简单的,动归思路有两种:
1:
用二维数组存放数字三角形;
D( r, j) : 第r行第 j 个数字(r,j从1 开始算)
MaxSum(r, j) : 从D(r,j)到底边的各条路径中最佳路径的数字之和,问题是就求MaxSum(1,1);
典型的递归问题D(r, j)出发,下一步只能走D(r+1,j)或者D(r+1, j+1)。故对于N行的三角形:if ( r == N)MaxSum(r,j) = D(r,j)elseMaxSum( r, j) = Max{ MaxSum(r+1,j), MaxSum(r+1,j+1) } + D(r,j);2: 如果每算出一个MaxSum(r,j)就保存起来,下次用到其值的时候直接取用,则可免去重复计算。
那么可以用 O(n2)时间完成计算。因为三角形的数字总数是 n(n+1)/2;这时,递归转化为递推;
下面呈现两种思路代码:
1:超时代码:
#include#include #define MAX 101 using namespace std; int D[MAX][MAX]; int n;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 main(){ int i,j; cin >> n; for(i=1;i<=n;i++)for(j=1;j<=i;j++) cin >> D[i][j]; cout << MaxSum(1,1) << endl;} 如果采用递规的方法,深度遍历每条路径,存在大量重复计算。则时间复杂度为 2n, 对于 n = 100行,肯定超时。
2:记忆递归
#include#include using namespace std;#define MAX 101int 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(i=1;i<=n;i++)for(j=1;j<=i;j++) { cin >> D[i][j]; maxSum[i][j] = -1;} cout << MaxSum(1,1) << endl;}
3:
#include#include using namespace std;#define MAX 101int D[MAX][MAX]; int n;int maxSum[MAX][MAX];int main() { int i,j; cin >> n; for(i=1;i<=n;i++)for(j=1;j<=i;j++) cin >> D[i][j]; for( int i = 1;i <= n; ++ i ) maxSum[n][i] = D[n][i]; for( int i = n-1; i>= 1; --i )for( int j = 1; j <= i; ++j ) maxSum[i][j] = max(maxSum[i+1][j],maxSum[i+1][j+1]) + D[i][j] cout << maxSum[1][1] << endl;} 人人为我”递推型动归程序
4:当然了,3中的代码也可以空间优化,从下往上找
#include#include using namespace std;#define MAX 101int D[MAX][MAX];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]; //maxSum指向第n行 for( int i = n-1; i>= 1; --i )for( int j = 1; j <= i; ++j ) maxSum[j] = max(maxSum[j],maxSum[j+1]) + D[i][j]; cout << maxSum[1] << endl;} 如果看不懂简单手推模拟一遍你就明白了,不难。。和3中代码类似,只是将二维转化为一维了;