力扣：120. 三角形最小路径和
给定一个三角形 triangle ，找出自顶向下的最小路径和。
每一步只能移动到下一行中相邻的结点上。相邻的结点 在这里指的是 下标 与 上一层结点下标 相同或者等于 上一层结点下标 + 1 的两个结点。也就是说，如果正位于当前行的下标 i ，那么下一步可以移动到下一行的下标 i 或 i + 1 。
方法1：动态规划
定义一个与原来数组有相同位数的二元数组，其中的成员，对应原二维数组的每个成员的最小路径
对于一行中的各个成员的最小路径的计算，而计算主要涉及三个部分，第一部分为左边靠边位置，第二部分为右边靠边的位置，其余为中间位置。
第一部分计算为：本行靠左成员的值 + 到达上一个（上面一行靠左）的最小路径
第二部分计算为：本行靠右成员的值 + 到达上一个（上面一行靠右）的最小路径
第三部分计算为：min(到达上面一个，上面靠左一个）路径最小值 + 本行成员的值
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
class Solution{
public:
int mininumtotal(vector<vector<int>>& triangle) {
int n = triangle.size();
vector<vector<int>> f(n, vector<int>(n));
f[0][0] = triangle[0][0];
for (int i = 1; i < n; ++i) {
f[i][0] = f[i - 1][0] + triangle[i][0];
for (int j = 1; j < i; ++j) {
f[i][j] = min(f[i - 1][j - 1], f[i - 1][j]) + triangle[i][j];
}
f[i][i] = f[i - 1][i - 1] + triangle[i][i];
}
return *std::min_element(f[n - 1].begin(), f[n - 1].end());
}
};
int main() {
Solution solution;
vector<vector<int>> triangle = {
{2},
{3,4},
{6,5,7},
{4,1,8,3}
};
int result = solution.mininumtotal(triangle);
cout << "mininum path sum is " << result << endl;
return 0;
}
方法二：动态规划+空间优化
使用二维数组
后一行中的成员路径值，只与本行以及前一行有关，可以定义两行n列的数组，将其值进行拷贝，直至最后只有最后两行中的成员路径数值
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
class Solution {
public:
int minimumTotal(vector<vector<int>>& triangle) {
int n = triangle.size();
vector<vector<int>> f(2, vector<int>(n));
f[0][0] = triangle[0][0];
for (int i = 1; i < n; ++i) {
int curr = i % 2;
int prev = 1 - curr;
f[curr][0] = f[prev][0] + triangle[i][0];
for (int j = 1; j < i; ++j) {
f[curr][j] = min(f[prev][j - 1], f[prev][j]) + triangle[i][j];
}
f[curr][i] = f[prev][i - 1] + triangle[i][i];
}
return *std::min_element(f[(n - 1) % 2].begin(), f[(n - 1) % 2].end());
}
};
int main()
{
Solution solution;
vector<vector<int>> triangle = {
{2},
{3,4},
{6,5,7},
{4,1,8,3}
};
int result = solution.minimumTotal(triangle);
cout << "mininum path sum == " << result << endl;
return 0;
}
使用一维数组
从上向下，从右向左计算，计算的结果，存储在一维数组中，覆盖上一行的结果
比如二行开始，
其首先计算的为f[1] = f[0] + triangle[1][1] ，存储为f[1]
再计算f[0] = f[0] + triangle[1][0]，存储为f[0]
计算第三行
其首先计算的为f[2] =f[1] + triangle[2][2] ，存储为f[2]
再计算的为f[1] = min(f[0],f[1]) + triangle[2][1] ，存储为f[1]
再计算f[0] = f[0] + triangle[2][0]，存储为f[0]
以此类推，计算到n行时，更新完成
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
class Solution {
public:
int mininumTotal(vector<vector<int>>& triangle) {
int n = triangle.size();
vector<int> f(n);
f[0] = triangle[0][0];
for (int i = 1; i < n; ++i) {
f[i] = f[i - 1] + triangle[i][i];
for (int j = i - 1; j > 0; --j) {
f[j] = min(f[j], f[j - 1]) + triangle[i][j];
}
f[0] = f[0] + triangle[i][0];
}
return *min_element(f.begin(), f.end());
}
};
int main()
{
Solution solution;
vector<vector<int>> triangle = {
{2},
{3,4},
{6,5,7},
{4,1,8,3}
};
int result = solution.mininumTotal(triangle);
cout << "mininum path sum == " << result << endl;
return 0;
}
