Triangle

Solutions

Dynamic Programming

Time: O(n^2)Space: O(n^2)

The dynamic programming approach involves creating a 2D array dp where dp[i][j] represents the minimum path sum from the top to the current position. We initialize the first row of dp with the first row of the triangle. Then, for each row from the second to the last, we calculate the minimum path sum for each position by considering the minimum path sum of the two adjacent positions in the previous row and adding the current value. Finally, we return the minimum value in the last row of dp.

int minimumTotal(vector<vector<int>>& triangle) {
  int n = triangle.size();
  vector<vector<int>> dp(n, vector<int>(n, 0));
  dp[0][0] = triangle[0][0];
  for (int i = 1;
  i < n;
  i++) {
    for (int j = 0;
    j <= i;
    j++) {
      if (j == 0) {
        dp[i][j] = dp[i-1][j] + triangle[i][j];
      }
      else if (j == i) {
        dp[i][j] = dp[i-1][j-1] + triangle[i][j];
      }
      else {
        dp[i][j] = min(dp[i-1][j-1], dp[i-1][j]) + triangle[i][j];
      }
    }
  }
  int min = INT_MAX;
  for (int num : dp[n-1]) {
    min = min(min, num);
  }
  return min;
}

Constraints:

Examples:

Solutions

Dynamic Programming

Follow-up: