Share my C++ solution and I don't think it belongs to DP


  • 0
    V
    class Solution {
    public:
        int minimumTotal(vector<vector<int>>& triangle) {
            int n = triangle.size();
            if (n < 1) return 0;
            
            vector<int> triangle_sum(n, 0);
            int i = 0, j = 0, min_sum = INT_MAX, t = 0;
            
            triangle_sum[0] = triangle[0][0];
            for (i = 1; i < n; ++i)
            {
                for (j = i; j >= 0; --j)
                {
                    if (j == i)
                        triangle_sum[j] = triangle_sum[j-1] + triangle[i][j];
                    else if (j == 0)
                        triangle_sum[j] += triangle[i][j];
                    else
                        triangle_sum[j] = min(triangle_sum[j-1], triangle_sum[j]) + triangle[i][j];
                }
            }
            
            for (i = 0; i < n; ++i)
                if (min_sum > triangle_sum[i])
                    min_sum = triangle_sum[i];
             
            return min_sum;       
        }
    };

Log in to reply
 

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