一、题目
有三种方法实现： 这里就求权值之和最大的，最小的类似就不分析了。
1.
自底向上
缺点：算法复杂，重复计算
2.
自顶向下
缺点
：重复计算，浪费时间
3.
动态规划 思路和自底向上、自顶向下一样，只不过开多一个数组
opt存储计算过的到达a[i][j]的权值之和最大的数
二、思路：
方法1：
自底向上
1.从最后一行出发，例如，最后一行的2：
如何得到走到2的权值之和最大数？（用
递归
）
那就要先得到走到左上角的数（7）的权值之和最大的数，正上方的数（4）的权值之和最大的数。
再比较两者哪个大，大的一个加上最后一行的数2，就是走到2的权值之和最大的数；
同样，如何得到走到7的权值之和最大的数？或者是走到4的权值之和的最大数
就要先得到7的左上角的数（8）的权值之和的最大数，和正上方的数（1）的权值之和的最大数，再
比较这两个权值之和哪个大，大的加上7；
……
一直
递推
到第一行的数a[0][0]，返回a[0][0]的值，然后
回归
，求得到达2的权值之和的最大数；
2.比较走到最后一行（4，5，2，6，5）的各个权值之和，取得权值之和最大的数，然后输出
实现程序：
// 数字三角形
// 7
// 3 8
// 8 1 0
// 2 7 4 4
// 4 5 2 6 5
// 找出从第一层到最后一层的一条路，使得经过的权值之和最小或者最大，
// 每一步只能向下或向右下方走。
// 第一种方法：自底向上的思路
// 缺点：算法有点复杂
// 思路：从下面一个数开始往上计算，取sum(i-1, j-1)和sum(i-1, j)的最大值（即前面的权值之和最大值），加上当前值
#include <iostream>
const int max = 100;
int a[max][max];
int sum(int i, int j);
int main(int argc, const char * argv[]) {
int m = 0;
int i, j, t, n;
std::cin >> n; // 行数
for(i = 0; i < n; i++) // 输入数字三角形
for(j = 0; j <= i; j++)
std::cin >> a[i][j];
for(j = n-1; j >= 0; j--) {
t = sum(n-1, j); // 计算走到最后一行每个数的权值之和
if(m < t)
m = t;
}
std::cout << m << std::endl;
return 0;
}
// 递归：求走到第i行和第j列的权值之和最大的数
int sum(int i, int j) {
int x, y;
if(i < j)
return 0;
if(i == 0)
return a[0][0];
else {
x = sum(i-1, j-1); // 求到达左上角的数的权值之和最大数
y = sum(i-1, j); // 求到达正上方的数的权值之和最大数
if(x > y)
return x+a[i][j];
else
return y+a[i][j];
}
}测试结果：
方法2：
自顶向下
和自底向上的思路刚好相反
1.从a[0][0]出发：
递推
：得到从最后一行到正下方a
[1][0]的权值之和最大的数
，和从最后一行到右下方
a[1][1]的权值之和最大的数
；
回归
：究竟
是最后一行到
达
a[1][0]的权值之和大
，还是最后一行到达
a[1][1]的权值之和大
？
取权值之和较大的，然后加上a[0][0]，就是所求的权值之和最大的数
那如何求得最后一行到a[1][0]的权值之和最大的数？或者是到a[1][1]的
同样，求最后一行到正下方的数a[2][0]的权值之和，然后求最后一行到右下方的数a[2][1]的权值之和；
取较大的权值之和，加上a[1][0]
…
一直
递推
，直到最后一行，然后返回最后一行的数
接着
，
回归
求得从最后一行到
a[0][0]的权值之和最大的数
。
2.实现程序：
// 数字三角形
// 7
// 3 8
// 8 1 0
// 2 7 4 4
// 4 5 2 6 5
// 找出从第一层到最后一层的一条路，使得经过的权值之和最小或者最大，
// 每一步只能向下或向右下方走。
// 第二种方法：自顶向下的思路
// 缺点：重复计算，浪费时间
#include <iostream>
const int max = 100;
int a[max][max];
int sum(int i, int j, int n); // 取得到达最后一行的权值之和最大的数
int main(int argc, const char * argv[]) {
int i, j, n;
std::cin >> n; // 输入行数
// 输入数字三角形
for(i = 0; i < n; i++)
for(j = 0; j <= i; j++)
std::cin >> a[i][j];
std::cout << sum(0, 0, n) << std::endl; // 调用函数
return 0;
}
// 取得到达最后一行的权值之和最大的数
int sum(int i, int j, int n) {
int x, y;
if(i == n-1) // 到最后一行，返回最后一行的数
return a[i][j];
else {
x = sum(i+1, j, n); // 求得最后一行到a[i+1][j]的权值之和最大的数
y = sum(i+1, j+1, n); // 求得最后一行到a[i+1][j+1]的权值之和最大的数
if(x>y) // 取权值之和较大的加上a[i][j]
return x+a[i][j];
else
return y+a[i][j];
}
}
方法3
：
动态规划
1.思路：和自底向上和自顶向下思路一样，只不过，用多一个数组opt存储计算过的到达a[i][j]的权值之和最大的数
2.实现方法1：自顶向下（结合动态规划）
// 数字三角形
// 7
// 3 8
// 8 1 0
// 2 7 4 4
// 4 5 2 6 5
// 找出从第一层到最后一层的一条路，使得经过的权值之和最小或者最大，
// 每一步只能向下或向右下方走。
// 第三种方法：记忆化搜索，递归，自顶向下
#include <iostream>
const int MAX = 100;
int a[MAX][MAX];
int opt[MAX][MAX];
int sum(int i, int j, int n); // 计算
int main(int argc, const char * argv[]) {
int i, j, n;
std::cin >> n;
memset(opt, 0, sizeof(opt)); // 清零
// 输入数字三角形
for(i = 0; i < n; i++)
for(j = 0; j <= i; j++)
std::cin >> a[i][j];
std::cout << sum(0, 0, n) << std::endl; // 调用函数，求得最大的权值之和
return 0;
}
// 递归：求最后一行到a[i][j]的权值之和最大的数
int sum(int i, int j, int n) {
if(opt[i][j] != 0) // 之前已经求过，直接返回
return opt[i][j];
if(i == n-1) { // 到达最后一行
opt[i][j] = a[i][j];
return a[i][j];
} else {
opt[i+1][j] = sum(i+1, j, n); // 求得最后一行到a[i+1][j]的权值之和最大的数
opt[i+1][j+1] = sum(i+1, j+1, n); // 求得最后一行到a[i+1][j+1]的权值之和最大的数
if(opt[i+1][j] > opt[i+1][j+1]) // 取权值之和较大的加上a[i][j]
return opt[i+1][j] + a[i][j]; // 最后一行到a[i][j]的权值之和最大的数
else
return opt[i+1][j+1] + a[i][j];
}
}
方法2：自底向上（结合动态规划）
#include <iostream>
const int max = 100;
int a[max][max];
int opt[max][max];
void MaxSum(int n); // 求得数字三角形中从第一行到各个位置的权值之和最大的数
int main(int argc, const char * argv[]) {
int i, j, n, t;
std::cin >> n; // 输入行数
memset(opt, 0, sizeof(opt)); // 清零
// 输入数字三角形
for(i = 0; i < n; i++)
for(j = 0; j <= i; j++)
std::cin >> a[i][j];
// 调用函数：求得数字三角形中从第一行到各个位置的权值之和最大的数
MaxSum(n);
t = 0;
// 比较最后一行的权值之和，找到最大的一个输出
for(i = 0; i < n; i++) {
if(t < opt[n-1][i])
t = opt[n-1][i];
}
std::cout << t << std::endl;
return 0;
}
// 求得数字三角形中从第一行到各个位置的权值之和最大的数
void MaxSum(int n) {
int i, j;
opt[0][0] = a[0][0];
for(i = 1; i < n; i++) {
// 计算每行第一个数的权值之和
opt[i][0] = opt[i-1][0] + a[i][0];
// 计算除开头和结尾之外的其他位置权值之和
for(j = 1; j < i - 1; j++) {
if(a[i][j]+opt[i-1][j] >= a[i][j]+opt[i-1][j-1])
opt[i][j] = a[i][j]+opt[i-1][j];
else
opt[i][j] = a[i][j]+opt[i-1][j-1];
}
// 计算每行最后一个数的权值之和
opt[i][i] = a[i][j]+opt[i-1][i-1];
}
}