[题目描述]
在一座山上,有很多很多珠宝,它们散落在山底通往山顶的每条道路上,不同道路上的珠宝的数目也各不相同.下图为一张藏宝地图:
7
3 8
8 1 0
2 7 4 4
4 5 2 6 5
”夺宝奇兵”从山下出发,到达山顶,如何选路才能得到最多的珠宝呢?在上图所示例子中,按照5->7->8->3->7的顺序,将得到最大值30
[输入]
第一行正整数N(100>=N>1),表示山的高度
接下来有N行非负整数,第i行有i个整数(1<=i<=N),表示山的第i层上从左到右每条路上的珠宝数目
[输出]
一个整数,表示从山底到山顶的所能得到的珠宝的最大数目.
[样例输入]
5
7
3 8
8 1 0
2 7 4 4
4 5 2 6 5
[样例输出]
30
下面将用四种方法来解决这道题：
方法一：递归函数，使用这种方法代码运行效率很低
#include<stdio.h> #define N 101 int g[N][N] = { 0 }; int n = 0; int max(int a, int b) { return a > b ? a : b; } int maxsum(int i, int j) { if (i == n) return g[i][j]; else { int x = maxsum(i + 1, j); int y = maxsum(i + 1, j + 1); return max(x, y) + g[i][j]; } } int main() { int i = 0, j = 0; scanf("%d", &n); //输入层数 for (i = 0; i < n; i++) { for (j = 0; j < i + 1; j++) { scanf("%d", &g[i][j]); } } printf("%d\n", maxsum(0, 0)); return 0; }
方法三：“人人为我”型递推
#include<stdio.h> #define N 101 int g[N][N] = { 0 }; int a[N][N] = { 0 }; int n = 0; int max(int a, int b) { return a > b ? a : b; } int main() { int i = 0, j = 0; scanf("%d", &n); //输入层数 for (i = 0; i < n; i++) { for (j = 0; j < i + 1; j++) { scanf("%d", &g[i][j]); } } for (j = 0; j < n; j++) { a[n - 1][j] = g[n - 1][j]; } for (i = n - 2; i >= 0; i--) { for (j = 0; j < i + 1; j++) { a[i][j] = max(a[i + 1][j], a[i + 1][j + 1]) + g[i][j]; } } printf("%d\n", a[0][0]); return 0; }
方法四：“我为人人 ”型递推，空间复杂度比方法三更低
#include<stdio.h> #define N 101 int g[N][N] = { 0 }; int a[N] = { 0 }; int n = 0; int max(int a, int b) { return a > b ? a : b; } int main() { int i = 0, j = 0; scanf("%d", &n); //输入层数 for (i = 0; i < n; i++) { for (j = 0; j < i + 1; j++) { scanf("%d", &g[i][j]); } } for (j = 0; j < n; j++) { a[j] = g[n - 1][j]; } for (i = n - 2; i >= 0; i--) { for (j = 0; j < i + 1; j++) { a[j] = max(a[j], a[j + 1]) + g[i][j]; } } printf("%d\n", a[0]); return 0; }
