数据结构
网络
RDBMS
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化学
生物学
数学
英语
经济学
心理学
社会科学
时尚知识
法律研究用 C++ 求后缀波兰表达式的值
假设我们有一个三角形。我们必须找到从上到下的最小路径和。在每一步中，我们都可以移动到下面一行的相邻数字。
例如，如果以下三角形为
[ [2], [3,4], [6,5,7], [4,1,8,3] ]
从上到下的最小路径和为 11 (2 + 3 + 5 + 1 = 11)。
我们来看看步骤
- 创建一个表，用于动态规划方法。
- n := 三角形的尺寸
- for i := n – 2 down to 0
- for j := 0 to i
- dp[j] := triangle[i, j] + dp[j] 和 dp[j + 1] 中的最小值
- for j := 0 to i
- return dp[0]
我们来看看以下实现以更好地理解
示例
class Solution {
public:
void printVector(vector <int>& v){
for(int i = 0; i < v.size(); i++)cout << v[i] << " ";
cout << endl;
}
int minimumTotal(vector<vector<int>>& triangle) {
vector <int> dp(triangle.back());
int n = triangle.size();
for(int i = n - 2; i >= 0; i--){
for(int j = 0; j <= i; j++){
dp[j] = triangle[i][j] + min(dp[j], dp[j + 1]);
}
// printVector(dp);
}
return dp[0];
}
};输入
[[2],[3,4],[6,5,7],[4,1,8,3]]
输出
11
更新日期： 31-Jan-2020
273 次浏览
广告