My 12ms c++ dp code


  • 0
    P

    class Solution {

    public:

    int minimumTotal(vector<vector<int>>& triangle) {
        int n = triangle.size();
        if (n==0) return 0;
        if (n==1) return triangle[0][0];
        for (int i=1; i<n; i++){
            triangle[i][0] += triangle[i-1][0];
            triangle[i][i] += triangle[i-1][i-1];
            for (int j = 1; j < i; j++){
                triangle[i][j] += min(triangle[i-1][j-1],triangle[i-1][j]); 
            }
        }
        return *min_element(triangle[n-1].begin(), triangle[n-1].end());
    }
    

    };


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.