LeetCode Daily Problem P120 Triangle Minimum Path Sum

---

Timeline

Timeline

2025-09-25

init

Dynamic Programming

---

Problem:

P120 Triangle Minimum Path Sum

https://leetcode.cn/problems/triangle/description/?envType=daily-question&envId=2025-09-25

Assume dp[i][j] represents the minimum path sum starting from row i+1, column j+1

• When j!=0 && j!=i

  $$dp[i][j] = min(dp[i-1][j-1] + dp[i-1][j]) + triangle[i][j]$$

• When j==0

  $$dp[i][j] = dp[i-1][0] + triangle[i][j]$$

• When j==i

  $$dp[i][j] = dp[i-1][j-1] + triangle[i][j]$$

Actually, for this problem, a one-dimensional array for dp is sufficient. After each layer is computed, it is no longer needed, and the previous layer can be overwritten.

#include <climits>
#include <vector>

using std::vector;

class Solution {
    public:
        int minimumTotal(vector<vector<int> > &triangle)
        {
                int n = triangle.size();
                int min = INT_MAX;
                vector<vector<int> > dp(n, vector<int>(n));
                // dp[i][j] represents the minimum value starting from row i+1, column j+1
                // When j!=0 && j!=i
                // dp[i][j] = min {dp[i-1][j-1] + dp[i-1][j]} + triangle[i][j]
                // When j==0, dp[i][j] = dp[i-1][0] + triangle[i][j]
                // When j==i, dp[i][j] = dp[i-1][j-1] + triangle[i][j]
                dp[0][0] = triangle[0][0];
                // Starting from the second row, i.e., i==1
                for (int i = 1; i < n; i++) {
                        for (int j = 0; j <= i; j++) {
                                if (j == 0) {
                                        dp[i][j] = dp[i - 1][0] + triangle[i][j];
                                } else if (j == i) {
                                        dp[i][j] = dp[i - 1][j - 1] + triangle[i][j];
                                } else {
                                        dp[i][j] = std::min(dp[i - 1][j - 1], dp[i - 1][j]) +
                                                   triangle[i][j];
                                }
                        }
                }
                for (int j = 0; j < n; j++) {
                        if (dp[n - 1][j] < min) {
                                min = dp[n - 1][j];
                        }
                }
                return min;
        }
};