120: Triangle
Medium

table of contents

This is the introductory dynamic programming question.

First, you start off with the bottom row:

vector<int> dp = triangle.back();

Then, you make your way up the triangle, iterating through each of the rows above and updating our dp array using the equation:

dp[j] = triangle[i][j] + min(dp[j], dp[j+1]);
// where i = row of the triangle
//       j = specific index of a row of the triangle

Adding in the for loops, we get:

for (int i = triangle.size()-2; i >= 0; --i) {
    for (int j = 0; j < triangle[i].size(); ++j) {
        dp[j] = triangle[i][j] + min(dp[j], dp[j+1]);
    }
}

Eventually, our answer will be present at dp[0] which we return:

return dp[0];

code

class Solution {
public:
    int minimumTotal(vector<vector<int>>& triangle) {
        vector<int> dp = triangle.back();
        for (int i = triangle.size()-2; i >= 0; --i) {
            for (int j = 0; j < triangle[i].size(); ++j) {
                dp[j] = triangle[i][j] + min(dp[j], dp[j+1]);
            }
        }
        return dp[0];
    }
};

complexity

time taken