leetcode 120. 三角形最小路径和 O(1)额外空间

清疚 2022-02-12 14:59 156阅读 0赞

**将方块时候的最小路径改成了三角将triangle直接改成dp数组不用开额外空间**  
**triangle\[i\]\[j\] += min(triangle\[i-1\]\[j\],triangle\[i-1\]\[j-1\]); 每一行除了首位位置**  
**首位和尾位就一条路径**  
**triangle\[i\]\[0\] += triangle\[i-1\]\[0\];**  
**triangle\[i\]\[triangle\[i\].size()-1\] += triangle\[i-1\]\[triangle\[i-1\].size()-1\];**

#include <iostream>
    #include <vector>
    #include <limits.h>
    using namespace std;
    
    class Solution { 
    public:
        int minimumTotal(vector<vector<int>>& triangle) { 
            if(triangle.size()==0 || triangle[0].size()==0){ 
                return 0;
            }else if(triangle.size()==1){ 
                return triangle[0][0];
            }
            for(int i=1;i<triangle.size();i++){ 
                triangle[i][0] += triangle[i-1][0];
                for(int j=1;j<triangle[i].size()-1;j++){ 
                    triangle[i][j] += min(triangle[i-1][j],triangle[i-1][j-1]);
                }
                triangle[i][triangle[i].size()-1] += triangle[i-1][triangle[i-1].size()-1];
            }
            int ret  = INT_MAX;
            for(int i=0;i<triangle[triangle.size()-1].size();i++){ 
                ret  = min(ret, triangle[triangle.size()-1][i]);
            }
            return ret;
        }
    };
    
    int main()
    { 
        vector< vector<int> >nums={ 
            { 2},
            { 3,4},
            { 6,5,7},
            { 4,1,8,3}
        };
        Solution Solution1;
        cout<<Solution1.minimumTotal(nums)<<endl;
        return 0;
    }

![在这里插入图片描述][20190429085714228.png]

[20190429085714228.png]: /images/20220212/0a798df71d984e7ea32a3cdd1c0870b6.png