120.triangle.md

120.三角形最小路径和

1. 描述：
   • 给定一个三角形，找出自顶向下的最小路径和。
   • 每一步只能移动到下一行中相邻的结点上。
   • 相邻的结点指的是，下标与上一层结点下标相同,或者等于上一层结点下标 +1的两个结点。
2. 实现
   • 动态规划，二维，8 ms。
   • 定义dp[i][j]是从点(i,j)到底边的最小路径和。
   • 从最后一行开始递推。

     class Solution {
     public:
         int minimumTotal(vector<vector<int>>& triangle) {
             int n=triangle.size();
             // dp[i][j] 表示从点(i,j) 到底边的最小路径和。
             vector<vector<int>>dp(n+1, vector<int>(n+1,0));
             int i,j;
             // 从三角形的最后一行开始递推。
             for(i=n-1; i>=0; i--){
                 for(j=0; j<=i; j++){
                     dp[i][j] = min(dp[i+1][j], dp[i+1][j+1]) + triangle[i][j];
                 }
             }
             return dp[0][0];
         }
     };
     

   • 空间复杂度减少一半以后，时间却变成了16 ms。

     class Solution {
     public:
         int minimumTotal(vector<vector<int>>& triangle) {
             int n=triangle.size();
             // 
             vector<int>dp(n+1, 0);
             int i,j;
             // 从三角形的最后一行开始递推。
             for(i=n-1; i>=0; i--){
                 for(j=0; j<=i; j++){
                     dp[j] = min(dp[j], dp[j+1]) + triangle[i][j];
                 }
             }
             return dp[0];
         }
     };