数据结构
网络
关系型数据库管理系统
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
JavaScript
PHP
物理
化学
生物
数学
英语
经济学
心理学
社会学
时尚研究
法律研究三角形中最小和路径的 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
更新于：20-12-2019
136 次浏览
广告