My DP solution


  • 0
    F
    int minimumTotal(vector<vector<int>>& triangle) {
            if (triangle.size() == 0) return 0;
            int h = triangle.size();
            int dp[10000];
            for (int i = 0; i < 10000; i++) dp[i] = 1e9;
            dp[1] = triangle[0][0];
            for (int i = 2; i <= h; i++) {
                for (int j = i; j >= 1; j--) {
                    dp[j] = min(dp[j], dp[j - 1]) + triangle[i - 1][j - 1];
                }
            }
            int mi = 1e9;
            for (int i = 1; i <= h; i++) mi = min(mi, dp[i]);
            return mi;
        }
    

Log in to reply
 

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