C ++中三角形的最小求和路径
问题陈述
给定一个三角形的数字结构，找到从上到下的最小路径总和。您可以将每一步移至下面一行中的相邻数字。
示例
如果输入为-
5 7 3 8 1 2 9 6 4 5
然后最小总和为13，如下所示-
5+3+1+4
算法
使用动态编程记忆技术
创建一维数组进行记忆即记忆
对于每K行，请使用以下公式-
memorization[i] = min( memorization[i], memorization[i+1]) + A[k][i];
示例
#include <bits/stdc++.h>
using namespace std;
int getMinSum(vector<vector<int>> &arr) {
int memorization[arr.size()];
int n = arr.size() - 1;
for (int i = 0; i < arr[n].size(); ++i) {
memorization[i] = arr[n][i];
}
for (int i = arr.size() - 2; i >= 0; --i) {
for (int j = 0; j < arr[i + 1].size() - 1; ++j) {
memorization[j] = arr[i][j] +
min(memorization[j],
memorization[j + 1]);
}
}
return memorization[0];
}
int main() {
vector<vector<int>> arr = {
{5},
{7, 3},
{8, 1, 2},
{9, 6, 4, 5}, };
cout << "Minimum sum path = " << getMinSum(arr) << endl;
return 0;
}当您编译并执行上述程序时。它产生以下输出-
输出结果
Minimum sum path = 13