Triangle Minimum Path Sum Using Dynamic Programming

94.2k
1

A triangular integer array contains one value in the first row, two values in the second row, and one additional value in every following row.

A path starts at the top value. From position (row, col), movement is allowed to (row + 1, col) or (row + 1, col + 1). Return the minimum sum among all valid paths ending in the last row.

Example 1

Input: triangle = [[2], [3, 4], [6, 5, 7], [4, 1, 8, 3]]
Output: 11
Explanation: Path 2 → 3 → 5 → 1 gives the minimum sum 11.

Example 2

Input: triangle = [[-10]]
Output: -10
Explanation: The only value forms the complete path.

Recursion

Every position offers the same small choice: move straight down or move diagonally down-right. Either move leaves a smaller copy of the original path problem, so recursion follows the triangle naturally.

State solve(row, col) represents the minimum path sum from (row, col) to the last row. The public method starts with solve(0, 0) because every valid path begins at the single top value. A last-row position already completes a path, so the triangle value becomes the base answer.

Algorithm

  • Define solve(row, col) as the minimum sum from one position to the last row, so every recursive state has one clear meaning.

  • Return triangle[row][col] at the last row because the current value completes a valid top-to-bottom path without another move.

  • Explore (row + 1, col) because a straight-down move preserves the current column.

  • Explore (row + 1, col + 1) because a diagonal down-right move advances one column.

  • Add the current triangle value to the smaller child result because a minimum path must choose exactly one allowed child.

  • Start with solve(0, 0) because the top value is the required starting position for every valid path.

Dry Run

Diagram 1
1 / 2

Diagram 1

Solution

#include <bits/stdc++.h>
using namespace std;
class Solution {
private:
// Returns the minimum path sum from a selected position.
int solve(int row, int col, vector<vector<int>>& triangle) {
int n = triangle.size();
// A last-row position completes a valid path.
if (row == n - 1) {
return triangle[row][col];
}
// A straight-down move keeps the current column.
int down = solve(row + 1, col, triangle);
// A diagonal move advances to the next column.
int diagonal = solve(row + 1, col + 1, triangle);
// The smaller child creates the minimum full path.
return triangle[row][col] + min(down, diagonal);
}
public:
// Returns the minimum top-to-bottom path sum.
int minimumTotal(vector<vector<int>>& triangle) {
// Every valid path starts at the single top value.
return solve(0, 0, triangle);
}
};
// Driver code
int main() {
vector<vector<int>> triangle = {{2}, {3, 4}, {6, 5, 7}, {4, 1, 8, 3}};
Solution obj;
cout << obj.minimumTotal(triangle);
return 0;
}

Note: Direct recursion may fail for large input values. Repeated subproblems create exponential work, so an online judge may report Time Limit Exceeded.

Complexity Analysis

Time Complexity: O(2N), where N is the number of rows in the triangle, because each state can branch into two recursive choices across at most N levels.

Space Complexity: O(N), because one active recursive path can contain at most one stack frame for each row.

Memoization

Different paths can arrive at the same position, so direct recursion calculates identical remaining paths many times. A table named dp saves each state answer after the first calculation and returns the saved value during later visits.

State meaning and recursive choices remain unchanged. A separate visited table marks completed states because valid negative path sums could match a numeric sentinel such as -1.

Algorithm

  • Create dp and visited tables with n rows and n columns, so saved answers remain separate from completion markers.

  • Return the triangle value at the last row because a final-row state already forms a complete remaining path.

  • Return dp[row][col] whenever visited[row][col] is marked, so repeated paths avoid another recursive expansion.

  • Explore the straight-down and diagonal child states with the unchanged recursive choices, preserving the original state meaning.

  • Add the current value to the smaller child answer because one of the two allowed moves must continue the path.

  • Store the calculated answer in dp[row][col] and mark visited[row][col], so later requests can reuse a proven result.

  • Start memoized recursion at (0, 0) because the single top position represents the complete problem.

Dry Run

Diagram 1
1 / 2

Diagram 1

Solution

#include <bits/stdc++.h>
using namespace std;
class Solution {
private:
// Returns a stored or calculated minimum path sum.
int solve(int row, int col, vector<vector<int>>& triangle,
vector<vector<int>>& dp, vector<vector<int>>& visited) {
int n = triangle.size();
// A last-row position completes a valid path.
if (row == n - 1) {
return triangle[row][col];
}
// A completed state can be reused safely.
if (visited[row][col] == 1) {
return dp[row][col];
}
// A straight-down move keeps the current column.
int down = solve(row + 1, col, triangle, dp, visited);
// A diagonal move advances to the next column.
int diagonal = solve(row + 1, col + 1, triangle, dp, visited);
// The smaller child creates the minimum full path.
dp[row][col] = triangle[row][col] + min(down, diagonal);
// A marker separates valid values from empty states.
visited[row][col] = 1;
// The saved answer represents the current state.
return dp[row][col];
}
public:
// Returns the minimum top-to-bottom path sum.
int minimumTotal(vector<vector<int>>& triangle) {
int n = triangle.size();
// The DP table stores one answer for every state.
vector<vector<int>> dp(n, vector<int>(n, 0));
// Markers preserve valid negative path sums.
vector<vector<int>> visited(n, vector<int>(n, 0));
// Every valid path starts at the single top value.
return solve(0, 0, triangle, dp, visited);
}
};
// Driver code
int main() {
vector<vector<int>> triangle = {{2}, {3, 4}, {6, 5, 7}, {4, 1, 8, 3}};
Solution obj;
cout << obj.minimumTotal(triangle);
return 0;
}

Complexity Analysis

Time Complexity: O(N2), where N is the number of rows in the triangle, because the triangle contains O(N2) reachable states and each state is computed once with constant work.

Space Complexity: O(N2), because the dp and visited tables store O(N²) values, while the recursion stack adds only O(N) space.

Tabulation

Memoization still uses a recursion stack. Tabulation removes recursive calls by placing the known last-row base states into dp and building parent answers upward.

Every parent needs only two answers from the row directly below. Bottom-up row order guarantees both child answers before a parent calculation, and dp[0][0] finally represents the complete problem.

Algorithm

  • Create a square table named dp with side length n, so every valid triangle position has storage for one minimum sum.

  • Copy the last triangle row into the last dp row because final-row positions need no further transition.

  • Process rows from the second-last row upward, so both child answers are complete before each parent state.

  • Visit columns from 0 through the current row index because only such positions belong to the triangular input.

  • Read dp[row + 1][col] and dp[row + 1][col + 1] because the two values represent every allowed continuation.

  • Store the current value plus the smaller child cost in dp[row][col], preserving the same choice used by recursion.

  • Return dp[0][0] because the top state covers every valid path from the required starting position.

Dry Run

Triangle Tabulation

Triangle Tabulation

Solution

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
// Returns the minimum path sum using bottom-up tabulation.
int minimumTotal(vector<vector<int>>& triangle) {
int n = triangle.size();
// The table stores one answer for every position.
vector<vector<int>> dp(n, vector<int>(n, 0));
// Last-row values form the base states.
for (int col = 0; col < n; col++) {
dp[n - 1][col] = triangle[n - 1][col];
}
// Parent states are calculated after both child states.
for (int row = n - 2; row >= 0; row--) {
// Only valid positions in the row need answers.
for (int col = 0; col <= row; col++) {
// The straight child keeps the current column.
int down = dp[row + 1][col];
// The diagonal child uses the next column.
int diagonal = dp[row + 1][col + 1];
// The smaller child creates the minimum path.
dp[row][col] = triangle[row][col] + min(down, diagonal);
}
}
// The top state represents the complete problem.
return dp[0][0];
}
};
// Driver code
int main() {
vector<vector<int>> triangle = {{2}, {3, 4}, {6, 5, 7}, {4, 1, 8, 3}};
Solution obj;
cout << obj.minimumTotal(triangle);
return 0;
}

Complexity Analysis

Time Complexity: O(N2), where N is the number of rows in the triangle, because the nested traversal processes each of the O(N2) positions exactly once.

Space Complexity: O(N2), because the dp table stores one value for every triangle position, while the iterative approach uses no recursion stack.

Space Optimization

Tabulation reads only the row directly below the active row. Older rows never contribute again, so two one-dimensional arrays can replace the full dp table.

Array front stores the completed child row, while array current receives the active parent row. Every current value is calculated before current replaces front, so both old child values remain available throughout the row.

Algorithm

  • Initialize front as a copy of the last triangle row because every final-row value is already a complete base answer.

  • Process rows from the second-last row upward, so front always holds the required child answers.

  • Create a fresh current array for each active row, preventing new parent values from overwriting child values too early.

  • Read front[col] and front[col + 1] because the two values represent every allowed continuation.

  • Store the current value plus the smaller continuation in current[col] because a minimum path selects the cheaper child.

  • Replace front with the completed current row only after every column is calculated, preserving valid children during the whole row.

  • Return front[0] after the top row because the remaining value represents the complete minimum path.

Dry Run

Triangle Space Optimization

Triangle Space Optimization

Solution

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
// Returns the minimum path sum using rolling rows.
int minimumTotal(vector<vector<int>>& triangle) {
int n = triangle.size();
// Final-row values form complete base paths.
vector<int> front = triangle[n - 1];
// Rows are reduced from the base toward the top.
for (int row = n - 2; row >= 0; row--) {
// Fresh storage preserves every child value.
vector<int> current(row + 1, 0);
// Only valid positions in the row need answers.
for (int col = 0; col <= row; col++) {
// The straight child keeps the current column.
int down = front[col];
// The diagonal child uses the next column.
int diagonal = front[col + 1];
// The smaller child creates the current answer.
current[col] = triangle[row][col] + min(down, diagonal);
}
// Shift the complete row into child-row storage.
front = current;
}
// The remaining top value is the complete answer.
return front[0];
}
};
// Driver code
int main() {
vector<vector<int>> triangle = {{2}, {3, 4}, {6, 5, 7}, {4, 1, 8, 3}};
Solution obj;
cout << obj.minimumTotal(triangle);
return 0;
}

Complexity Analysis

Time Complexity: O(N2), where N is the number of rows in the triangle, because every triangle position is processed exactly once.

Space Complexity: O(N), because front and current store at most two rows of up to N values each, while older DP rows are discarded.

Interview follow-up Questions

Yes. Negative values remain valid path contributions. A separate visited table avoids confusion between an uncalculated state and a valid negative result.

Dynamic Programming

Read Similar Blogs

Dynamic Programming

Largest Divisible Subset

Given an array nums containing distinct positive integers, return a maximum-length subset. For every pair of values first and second in the subset, either first % second == 0 or secon...

73.5k
Dynamic Programming

Best Time to Buy and Sell Stock with Transaction Fee

An array prices stores a stock price for each day, and an integer fee gives the cost of one completed transaction. Any number of transactions may be completed, but only one share may be held at a t...

65.7k
Dynamic Programming

Check If a Subset with the Target Sum Exists

Given an array arr containing n positive integers and a non-negative integer target , select each array position at most once. Return true if the sum of selected elements equals target ; otherwise,...

55.1k
Comments0