1021:数字三角形

总时间限制: 1000ms 内存限制: 65536kB

描述

7 3 8 8 1 0 2 7 4 4 4 5 2 6 5

给出了一个数字三角形。从三角形的顶部到底部有很多条不同的路径。对于每条路径，把路径上面的数加起来可以得到一个和，你的任务就是找到最大的和。

注意：路径上的每一步只能从一个数走到下一层上和它最近的左边的那个数或者右边的那个数。

输入

输入的是一行是一个整数N (1 < N <= 100)，给出三角形的行数。下面的N行给出数字三角形。数字三角形上的数的范围都在0和100之间。

输出

输出最大的和。

样例输入

5 7 3 8 8 1 0 2 7 4 4 4 5 2 6 5

样例输出

30 递归程序解 //递归解 #include<bits/stdc++.h> using namespace std; const int N = 101; int map_[N][N], n; int max_sum(int i, int j) { if (i == n) return map_[i][j]; int x, y; x = max_sum(i+1, j); y = max_sum(i+1, j+1); return max(x, y) + map_[i][j]; } int main () { scanf("%d", &n); for (int i = 1; i <= n; i++) for (int j = 1; j <= i; j++) scanf("%d", &map_[i][j]); printf("%d", max_sum(1, 1)); return 0; }

为什么超时 答案：大量重复计算 7(1) 1 3(1) 8(1) 2 8(1) 1(2) 0(1) 4 2(1) 7(3) 4(3) 4(1) 8 4(1) 5(4) 2(6) 6(4) 5(1) 16 如果采用递归方法，深度遍历每条路径存在大量重复计算。底行时间复杂度2^n-1,总时间复杂度2ⁿ,对于n=100行时，肯定超时。

改进 如果每算出一个Max_Sum(r，j)就保存起来，下次用 到其值的时候直接取用，则可免去重复计算。那么 可以用O(n²)时间完成计算。因为三角形的数字总 数是n(n+1)/2.

记忆递归型动归程序解 #include<bits/stdc++.h> using namespace std; const int N = 101; int map_[N][N], maxSum[N][N], n; int max_sum(int i, int j) { if (maxSum[i][j] != -1) return maxSum[i][j]; if (i == n) maxSum[i][j] = map_[i][j]; else { int x = max_sum(i+1, j); int y = max_sum(i+1, j+1); maxSum[i][j] = max(x, y) + map_[i][j]; } return maxSum[i][j]; } int main () { scanf("%d", &n); for (int i = 1; i <= n; i++) for (int j = 1; j <= i; j++) { scanf("%d", &map_[i][j]); maxSum[i][j] = -1; } printf("%d", max_sum(1, 1)); return 0; } 递归转成递推 #include<bits/stdc++.h> using namespace std; const int N = 101; int map_[N][N], maxSum[N][N], n; int main () { scanf("%d", &n); for (int i = 1; i <= n; i++) for (int j = 1; j <= i; j++) scanf("%d", &map_[i][j]); for (int i = 1; i <= n; i++) maxSum[n][i] = map_[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]) + map_[i][j]; printf("%d", maxSum[1][1]); return 0; } 空间优化 没必要用二维maxSum数组存储每一个Max_Sum(r.j),只要从底层一行行向上递推，那么只要一维数组maxSum[100]即可,即只要存储一行的MaxSum值就 可以。 节省空间，时间复杂度不变O(n²)。 #include<bits/stdc++.h> using namespace std; const int N = 101; int map_[N][N], n; int *maxSum; int main () { scanf("%d", &n); for (int i = 1; i <= n; i++) for (int j = 1; j <= i; j++) scanf("%d", &map_[i][j]); maxSum = map_[n]; for (int i = n-1; i >= 1; i--) for (int j = 1; j <= i; j++) maxSum[j] = max(maxSum[j], maxSum[j+1]) + map_[i][j]; printf("%d", maxSum[1]); return 0; }