关键词：数塔问题
一、自底向上
题目描述
给出一个三角形，计算从三角形顶部到底部的最小路径和，每一步都可以移动到下面一行相邻的数字，
例如，给出的三角形如下：
[
[2],
[3,4],
[6,5,7],
[4,1,8,3]
]
最小的从顶部到底部的路径和是2 + 3 + 5 + 1 = 11。
注意：
如果你能只用O（N）的额外的空间来完成这项工作的话，就可以得到附加分，其中N是三角形中的行总数。
解题思路：
起初走了弯路，试图自顶向下解决问题。增加时间和空间消耗，且开辟dp[][]的额外空间，无法初始化（初始化为最大值，才能用循环找到最小的）。
另外，我的思路是从第二行开始，每一行中，每一个元素加上其上一行元素的相邻元素，就会出现每一行边界没有相邻元素的情况，使得多出条件判断程序变复杂。
参考了大佬们的思路：自底向上。
- 将输入的三角形看作一个二维数组，第i行的元素索引为[0...i]
- 从倒数第2行（n - 2行）开始，每一个元素的值覆盖为下一行与他相邻的左右两个元素中较小的数加上它本身
（保证从倒数第二行向上，每一行中每一个元素triangle[i][j]，其下一行，都有两个元素与他相邻:triangle[i+1][j], triangle[i+1][j+1]）
上代码：
class Solution {
public:
int minimumTotal(vector<vector<int> > &triangle) {
int n = triangle.size();
//自底向上,逐个修改每个位置的值
//如何修改？和下一行相邻两个数中较小的相加之和，覆盖这个数本身
for(int i = n - 2; i >= 0; i--){
for(int j = 0; j <= i; j++){
triangle[i][j] += min(triangle[i+1][j], triangle[i+1][j+1]);
}
}
return triangle[0][0];
}
};二、自上而下
https://www.cnblogs.com/fluxation/p/12693486.html
7
3 8
8 1 0
2 7 4 4
4 5 2 6 5有一个r行的数塔，数塔上有若干数字。问从数塔的最高点到底部，在所有的路径中，经过的数字的和最大为多少？
如上图，是一个5行的数塔，其中7—3—8—7—5的路径经过数字和最大，为30。
解法思路：
面对数塔问题，使用贪心算法显然是行不通的，比如给的样例，如果使用贪心算法，那选择的路径应当是7—8—1—7—5，其经过数字和只有28，并不是最大。而用深搜DFS很容易算出时间复杂度为O(2N-1)（因为每个数字都有向左下和右下两种选择），行数一多必定超时。
所以，数塔问题需要使用动态规划算法。
- 我们可以从上往下遍历。
可以发现，要想经过一个数字，只能从左上角或右上角的数字往下到达。
所以显然，经过任一数字A时，路径所经过的数字最大和——是这个数字A左上方的数字B以及右上方的数字C两个数字中，所能达到的数字最大和中较大的那一个，再加上该数字A。
故状态转移方程为：
其中i，j表示行数和列数，dp表示储存的最大和，num表示位置上的数字。
以样例来说明：在经过第三行的数字1时，我们先看它左上角的数字3和右上角的数字8其能达到的最大和。3显然只有7—3一条路径，故最大和是10；8显然也只有7—8一条路径，其最大和是15；两者中较大的是15，故经过1所能达到的最大和是15+1=16。
这样一步步向下遍历，最后经过每一个位置所能达到的最大和都求出来了，只要从最底下的一行里寻找最大值并输出即可。
- 我们也可以从下往上遍历。
一条路径不管是从上往下走还是从下往上走，其经过的数字和都是一样的，所以这题完全可以变成求——从最底层到最高点所经过的最大数字和。
其写法与顺序遍历是一样的，只是状态转移时，变成从该数字的左下角和右下角来取max了。逆序遍历的写法相比于顺序遍历优点在于：少了最后一步求最后一行max的过程，可以直接输出最高点所储存的值。
#include <stdio.h>
#include <algorithm>
using namespace std;//这里以顺序遍历为例
int num[1005][1005];//用于储存数塔每个位置的数字
int dp[1005][1005];//用于储存经过数塔每个位置所能达到的最大和
int main()
{
int r;
scanf("%d",&r);//输入数塔行数
for(int i=1;i<=r;i++)
for(int j=1;j<=i;j++)
scanf("%d",&num[i][j]);
//输入数塔数据，注意i和j要从1开始，防止数组越界
for(int i=1;i<=r;i++)//共计r行
for(int j=1;j<=i;j++)//每行有j个数字
dp[i][j]=max(dp[i-1][j],dp[i-1][j-1])+num[i][j];
//经过该数字的最大和，为左上角和右上角中的max，再加上该数字
int ans=0;
for(int i=1;i<=r;i++)
ans=max(ans,dp[r][i]);//从最后一行中找到最大数
printf("%d\n",ans);//就是答案
return 0;
}
京公网安备 11010502036488号