用C ++评估波兰语反向符号

假设我们有一个三角形。我们必须找到从上到下的最小路径总和。在每一步中，我们都可以移至下一行的相邻数字。

例如，如果下面的三角形像

[
   [2],
   [3,4],
   [6,5,7],
   [4,1,8,3]
]

从上到下的最小路径总和为11（2 + 3 + 5 +1 = 11）。

让我们看看步骤

• 创建一个表以用于动态编程方法。

• n：=三角形的大小

• 对于i：= n – 2降至0

• dp [j]：=三角形[i，j] + dp [j]和dp [j +1]的最小值

• 对于j：= 0到i

• 返回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