Minimum path sum in Triangular Grid (DP 11)

In this article, we will solve the most asked coding interview problem: Minimum path sum in Triangular Grid

Problem Link: Fixed Starting and Ending Point

Problem Description: 

We are given a Triangular matrix. We need to find the minimum path sum from the first row to the last row.

At every cell we can move in only two directions: either to the bottom cell (↓) or to the bottom-right cell(↘)

Examples
Example:

Practice:

Disclaimer: Don’t jump directly to the solution, try it out yourself first.

Memorization approach Tabulation approach Space Optimization

Expand any one approach by clicking the given options in the bar. Clicking one approach on bar, closes all other expands. You can manually expand more than one approach at a time

Memorization Approach
Algorithm / Intuition

This question is a slight modification of the question discussed in Minimum Path Sum in a Grid. In the previous problem, we were given a rectangular matrix whereas here the matrix is in the form of a triangle. Moreover, we don’t have a fixed destination, we need to return the minimum sum path from the top cell to any cell of the bottom row.

Why a Greedy Solution doesn’t work?

As we have to return the minimum path sum, the first approach that comes to our mind is to take a greedy approach and always form a path by locally choosing the cheaper option.

This approach will not give us the correct answer. Let us look at this example to understand:

At every cell, we have two choices: to move to the bottom cell or move to the bottom-right cell. Our ultimate aim is to provide a path that provides us the least path sum. Therefore at every cell, we will make the choice to move which costs us less.

  • Figure on the left gives us a greedy solution, where we move by taking the local best choice.
  • Figure on the right gives us a non-greedy solution.

We can clearly see the problem with the greedy solution. Whenever we are making a local choice, we may tend to choose a path that may cost us way more later.

Therefore, the other alternative left to us is to generate all the possible paths and see which is the path with the minimum path sum. To generate all paths we will use recursion.

Steps to form the recursive solution: 

We will first form the recursive solution by the three points mentioned in Dynamic Programming Introduction

Step 1: Express the problem in terms of indexes.

We are given a triangular matrix with the number of rows equal to N.

We can define the function with two parameters i and j, where i and j represent the row and column of the matrix.

Now our ultimate aim is to reach the last row. We can define f(i,j) such that it gives us the minimum path sum from the cell [i][j] to the last row.

We want to find f(0,0) and return it as our answer.

Base Case:

There will be a single base case:

  • When i == N-1, that is when we have reached the last row, so the min path from that cell to the last row will be the value of that cell itself, hence we return mat[i][j].

At every cell, we have two options to move to the bottom cell(↓) or to the bottom-right cell(↘). If we closely observe the triangular grid, at max we can reach the last row from where we return so we will not be able to go move out of the index of the grid. Therefore only one base condition is required.

The pseudocode till this step will be:

Step 2: Try out all possible choices at a given index.

At every index we have two choices, one to go to the bottom cell(↓) other to the bottom-right cell(↘). To go to the bottom, we will increase i by 1, and to move towards the bottom-right we will increase both i and j by 1.

Now when we get our answer for the recursive call (f(i+1,j) or f(i+1,j+1)), we need to also add the current cell value to it as we have to include it too for the current path sum.

Step 3:  Take the maximum of all choices

As we have to find the minimum path sum of all the possible unique paths, we will return the minimum of the choices(down and diagonal) 

The final pseudocode after steps 1, 2, and 3:

Steps to memoize a recursive solution:

If we draw the recursion tree, we will see that there are overlapping subproblems. In order to convert a recursive solution the following steps will be taken:

  1. Create a dp array of size [N][N]
  2. Whenever we want to find the answer of a particular row and column (say f(i,j)), we first check whether the answer is already calculated using the dp array(i.e dp[i][j]!= -1 ). If yes, simply return the value from the dp array.
  3. If not, then we are finding the answer for the given values for the first time, we will use the recursive relation as usual but before returning from the function, we will set dp[i][j] to the solution we get.
Code

#include <bits/stdc++.h>
using namespace std;

// Function to find the minimum path sum recursively with memoization
int minimumPathSumUtil(int i, int j, vector<vector<int> > &triangle, int n,
                       vector<vector<int> > &dp) {
    // If the result for this cell is already calculated, return it
    if (dp[i][j] != -1)
        return dp[i][j];

    // If we're at the bottom row, return the value of the current cell
    if (i == n - 1)
        return triangle[i][j];

    // Calculate the sum of two possible paths: going down and going diagonally
    int down = triangle[i][j] + minimumPathSumUtil(i + 1, j, triangle, n, dp);
    int diagonal = triangle[i][j] + minimumPathSumUtil(i + 1, j + 1, triangle, n, dp);

    // Store the minimum of the two paths in the dp table and return it
    return dp[i][j] = min(down, diagonal);
}

// Function to find the minimum path sum in the given triangle
int minimumPathSum(vector<vector<int> > &triangle, int n) {
    // Create a memoization table to store computed results
    vector<vector<int> > dp(n, vector<int>(n, -1));
    // Call the recursive function to find the minimum path sum
    return minimumPathSumUtil(0, 0, triangle, n, dp);
}

int main() {
    // Define the triangle as a 2D vector
    vector<vector<int> > triangle{{1},
                                   {2, 3},
                                   {3, 6, 7},
                                   {8, 9, 6, 10}};

    // Get the number of rows in the triangle
    int n = triangle.size();

    // Call the minimumPathSum function and print the result
    cout << minimumPathSum(triangle, n);

    return 0;
}


import java.util.*;

class TUF {
    // Function to find the minimum path sum in the triangle using dynamic programming
    static int minimumPathSumUtil(int i, int j, int[][] triangle, int n, int[][] dp) {
        // Check if the result for the current position (i, j) is already calculated
        if (dp[i][j] != -1)
            return dp[i][j];

        // If we are at the bottom row, return the value in the triangle
        if (i == n - 1)
            return triangle[i][j];

        // Calculate the minimum path sum by recursively considering two possible paths: down and diagonal
        int down = triangle[i][j] + minimumPathSumUtil(i + 1, j, triangle, n, dp);
        int diagonal = triangle[i][j] + minimumPathSumUtil(i + 1, j + 1, triangle, n, dp);

        // Store the result in the dp array and return the minimum of the two paths
        return dp[i][j] = Math.min(down, diagonal);
    }

    // Function to find the minimum path sum in the triangle
    static int minimumPathSum(int[][] triangle, int n) {
        // Create a 2D array to store computed results, initialize with -1
        int dp[][] = new int[n][n];
        for (int row[] : dp)
            Arrays.fill(row, -1);

        // Call the utility function to find the minimum path sum starting from the top
        return minimumPathSumUtil(0, 0, triangle, n, dp);
    }

    public static void main(String args[]) {
        int triangle[][] = {{1},
                            {2, 3},
                            {3, 6, 7},
                            {8, 9, 6, 10}};

        int n = triangle.length;

        // Call the minimumPathSum function and print the result
        System.out.println(minimumPathSum(triangle, n));
    }
}


def minimumPathSumUtil(i, j, triangle, n, dp):
    # Check if we have already computed the minimum path sum for this cell
    if dp[i][j] != -1:
        return dp[i][j]

    # If we are at the bottom of the triangle, return the value in the current cell
    if i == n - 1:
        return triangle[i][j]

    # Calculate the minimum path sum by considering two possible moves: down and diagonal
    down = triangle[i][j] + minimumPathSumUtil(i + 1, j, triangle, n, dp)
    diagonal = triangle[i][j] + minimumPathSumUtil(i + 1, j + 1, triangle, n, dp)

    # Store the computed minimum path sum in the memoization table
    dp[i][j] = min(down, diagonal)
    return dp[i][j]

# Define a wrapper function to initialize memoization table and start the computation
def minimumPathSum(triangle, n):
    dp = [[-1 for j in range(n)] for i in range(n)]  # Initialize a memoization table with -1
    return minimumPathSumUtil(0, 0, triangle, n, dp)  # Start the recursive computation

# Define the main function where you set up the triangle and call the minimumPathSum function
def main():
    triangle = [[1], [2, 3], [3, 6, 7], [8, 9, 6, 10]]
    n = len(triangle)

    # Call the minimumPathSum function and print the result
    print(minimumPathSum(triangle, n))

# Check if this script is the main program entry point
if __name__ == "__main__":
    main()  # Call the main function to start the program


function minimumPathSumUtil(i, j, triangle, n, dp) {
  // If the result is already computed, return it
  if (dp[i][j] !== -1) {
    return dp[i][j];
  }

  // If we are at the last row, return the value in the triangle
  if (i === n - 1) {
    return triangle[i][j];
  }

  // Calculate the minimum path sum by moving down and diagonally
  const down = triangle[i][j] + minimumPathSumUtil(i + 1, j, triangle, n, dp);
  const diagonal = triangle[i][j] + minimumPathSumUtil(i + 1, j + 1, triangle, n, dp);

  // Store the result in the DP array and return it
  dp[i][j] = Math.min(down, diagonal);
  return dp[i][j];
}

function minimumPathSum(triangle, n) {
  // Initialize the DP array with -1 values
  const dp = new Array(n).fill().map(() => new Array(n).fill(-1));
  return minimumPathSumUtil(0, 0, triangle, n, dp);
}

function main() {
  const triangle = [
    [1],
    [2, 3],
    [3, 6, 7],
    [8, 9, 6, 10]
  ];

  const n = triangle.length;

  console.log(minimumPathSum(triangle, n));
}

// Call the main function to execute the code
main();

Output: 14

Complexity Analysis

Time Complexity: O(N*N)

Reason: There are two nested loops

Space Complexity: O(N*N)

Reason: We are using an external array of size ‘N*N’. The stack space will be eliminated.

Tabulation Approach
Algorithm / Intuition

Steps to convert Recursive Solution to Tabulation one.

Recursion/Memoization is a top-down approach whereas tabulation is a bottom-up approach. As in recursion/memoization, we have moved from 0 to N-1, in tabulation we move from N-1 to 0, i.e the last row to the first one.

The steps to convert to the tabular solution are given below:

  • Declare a dp[] array of size [N][N].
  • First initialize the base condition values, i.e the last row of the dp matrix to the last row of the triangle matrix.
  • Our answer should get stored in dp[0][0]. We want to move from the last row to the first row. So that whenever we compute values for a cell, we have all the values required to calculate it.
  • If we see the memoized code, the values required for dp[i][j] are dp[i+1][j] and dp[i+1][j+1]. So we only need the values from the ‘i+1’ row.
  • We have already filled the last row (i=N-1), if we start from row ‘N-2’ and move upwards we will find the values correctly.
  • We can use two nested loops to have this traversal.
Code

#include <bits/stdc++.h>
using namespace std;

// Function to find the minimum path sum in the given triangle using dynamic programming
int minimumPathSum(vector<vector<int> > &triangle, int n) {
    // Create a 2D DP (dynamic programming) array to store minimum path sums
    vector<vector<int> > dp(n, vector<int>(n, 0));

    // Initialize the bottom row of dp with the values from the triangle
    for (int j = 0; j < n; j++) {
        dp[n - 1][j] = triangle[n - 1][j];
    }

    // Iterate through the triangle rows in reverse order
    for (int i = n - 2; i >= 0; i--) {
        for (int j = i; j >= 0; j--) {
            // Calculate the minimum path sum for the current cell
            int down = triangle[i][j] + dp[i + 1][j];
            int diagonal = triangle[i][j] + dp[i + 1][j + 1];

            // Store the minimum of the two possible paths in dp
            dp[i][j] = min(down, diagonal);
        }
    }

    // The top-left cell of dp now contains the minimum path sum
    return dp[0][0];
}

int main() {
    // Define the triangle as a 2D vector
    vector<vector<int> > triangle{{1},
                                   {2, 3},
                                   {3, 6, 7},
                                   {8, 9, 6, 10}};

    // Get the number of rows in the triangle
    int n = triangle.size();

    // Call the minimumPathSum function and print the result
    cout << minimumPathSum(triangle, n);

    return 0;
}


import java.util.*;

class TUF {
    // Function to find the minimum path sum in the triangle using dynamic programming
    static int minimumPathSum(int[][] triangle, int n) {
        // Create a 2D array to store intermediate results
        int dp[][] = new int[n][n];

        // Initialize the bottom row of dp with the values from the bottom row of the triangle
        for (int j = 0; j < n; j++) {
            dp[n - 1][j] = triangle[n - 1][j];
        }

        // Starting from the second to last row, calculate the minimum path sum for each element
        for (int i = n - 2; i >= 0; i--) {
            for (int j = i; j >= 0; j--) {
                // Calculate the two possible paths: moving down or moving diagonally
                int down = triangle[i][j] + dp[i + 1][j];
                int diagonal = triangle[i][j] + dp[i + 1][j + 1];

                // Store the minimum of the two paths in dp
                dp[i][j] = Math.min(down, diagonal);
            }
        }

        // The result is stored at the top of dp array
        return dp[0][0];
    }

    public static void main(String args[]) {
        int triangle[][] = {{1},
                            {2, 3},
                            {3, 6, 7},
                            {8, 9, 6, 10}};

        int n = triangle.length;

        // Call the minimumPathSum function and print the result
        System.out.println(minimumPathSum(triangle, n));
    }
}


def minimum_path_sum(triangle, n):
    # Create a 2D array dp to store minimum path sums
    dp = [[0 for j in range(n)] for i in range(n)]
    
    # Initialize the bottom row of dp with the values from the last row of the triangle
    for j in range(n):
        dp[n - 1][j] = triangle[n - 1][j]
    
    # Start from the second-to-last row and work upwards
    for i in range(n - 2, -1, -1):
        for j in range(i, -1, -1):
            # Calculate the minimum path sum for the current cell by considering two possible moves: down and diagonal
            down = triangle[i][j] + dp[i + 1][j]
            diagonal = triangle[i][j] + dp[i + 1][j + 1]
            
            # Store the minimum of the two possible moves in dp
            dp[i][j] = min(down, diagonal)
    
    # The minimum path sum will be stored in dp[0][0] after the loops
    return dp[0][0]

def main():
    # Define the input triangle and its size
    triangle = [[1], [2, 3], [3, 6, 7], [8, 9, 6, 10]]
    n = len(triangle)
    
    # Call the minimum_path_sum function and print the result
    print(minimum_path_sum(triangle, n))

if __name__ == '__main__':
    main()


function minimumPathSum(triangle, n) {
  // Initialize the DP array with all zeros
  const dp = new Array(n).fill().map(() => new Array(n).fill(0));

  // Initialize the bottom row of the DP array with the values from the triangle
  for (let j = 0; j < n; j++) {
    dp[n - 1][j] = triangle[n - 1][j];
  }

  // Start from the second-to-last row and work upwards
  for (let i = n - 2; i >= 0; i--) {
    for (let j = 0; j <= i; j++) {
      // Calculate the minimum path sum by considering the down and diagonal moves
      const down = triangle[i][j] + dp[i + 1][j];
      const diagonal = triangle[i][j] + dp[i + 1][j + 1];

      // Store the minimum of down and diagonal in the DP array
      dp[i][j] = Math.min(down, diagonal);
    }
  }

  // The minimum path sum will be stored in the top-left corner of the DP array
  return dp[0][0];
}

function main() {
  const triangle = [
    [1],
    [2, 3],
    [3, 6, 7],
    [8, 9, 6, 10]
  ];

  const n = triangle.length;

  console.log(minimumPathSum(triangle, n));
}

// Call the main function to execute the code
main();

Output: 14

Complexity Analysis

Time Complexity: O(N*N)

Reason: There are two nested loops

Space Complexity: O(N*N)

Reason: We are using an external array of size ‘N*N’. The stack space will be eliminated.

Space Optimization Approach
Algorithm / Intuition

If we closely look the relation,

dp[i][j] = matrix[i][j] + min(dp[i+1][j] + dp[i+1][j+1]))

We see that we only need the next row, in order to calculate dp[i][j]. Therefore we can space optimize it.

Initially we can take a dummy row ( say front). We initialize this row to the triangle matrix’s last row( as done in tabulation).

Now the current row(say cur) only needs the front row’s value in order to calculate dp[i][j].

At last, front [0] will give us the required answer.

Code

#include <bits/stdc++.h>
using namespace std;

// Function to find the minimum path sum in the given triangle using dynamic programming
int minimumPathSum(vector<vector<int>> &triangle, int n) {
    // Create two arrays to store the current and previous row values
    vector<int> front(n, 0); // Represents the previous row
    vector<int> cur(n, 0);   // Represents the current row
    
    // Initialize the front array with values from the last row of the triangle
    for (int j = 0; j < n; j++) {
        front[j] = triangle[n - 1][j];
    }
    
    // Iterate through the triangle rows in reverse order
    for (int i = n - 2; i >= 0; i--) {
        for (int j = i; j >= 0; j--) {
            // Calculate the minimum path sum for the current cell
            int down = triangle[i][j] + front[j];
            int diagonal = triangle[i][j] + front[j + 1];
            
            // Store the minimum of the two possible paths in the current row
            cur[j] = min(down, diagonal);
        }
        // Update the front array with the values from the current row
        front = cur;
    }
    
    // The front array now contains the minimum path sum from the top to the bottom of the triangle
    return front[0];
}

int main() {
    // Define the triangle as a 2D vector
    vector<vector<int>> triangle{{1},
                                  {2, 3},
                                  {3, 6, 7},
                                  {8, 9, 6, 10}};

    // Get the number of rows in the triangle
    int n = triangle.size();

    // Call the minimumPathSum function and print the result
    cout << minimumPathSum(triangle, n);

    return 0;
}


import java.util.*;

class TUF {
    // Function to find the minimum path sum in the triangle using dynamic programming
    static int minimumPathSum(int[][] triangle, int n) {
        // Create two arrays to store intermediate results: front and cur
        int[] front = new int[n]; // Stores the results for the current row
        int[] cur = new int[n];   // Stores the results for the next row

        // Initialize the front array with the values from the bottom row of the triangle
        for (int j = 0; j < n; j++) {
            front[j] = triangle[n - 1][j];
        }

        // Starting from the second to last row, calculate the minimum path sum for each element
        for (int i = n - 2; i >= 0; i--) {
            for (int j = i; j >= 0; j--) {
                // Calculate the two possible paths: moving down or moving diagonally
                int down = triangle[i][j] + front[j];
                int diagonal = triangle[i][j] + front[j + 1];

                // Store the minimum of the two paths in the cur array
                cur[j] = Math.min(down, diagonal);
            }
            
            // Update the front array with the values from the cur array for the next row
            front = cur.clone();
        }

        // The result is stored at the top of the front array
        return front[0];
    }

    public static void main(String args[]) {
        int triangle[][] = {{1},
                            {2, 3},
                            {3, 6, 7},
                            {8, 9, 6, 10}};

        int n = triangle.length;

        // Call the minimumPathSum function and print the result
        System.out.println(minimumPathSum(triangle, n));
    }
}


def minimumPathSum(triangle, n):
    # Initialize two lists: front and cur to represent the current and previous rows in dp
    front = [0] * n  # This represents the previous row
    cur = [0] * n    # This represents the current row
    
    # Initialize the bottom row of dp (front) with the values from the last row of the triangle
    for j in range(n):
        front[j] = triangle[n - 1][j]
    
    # Start from the second-to-last row and work upwards
    for i in range(n - 2, -1, -1):
        for j in range(i, -1, -1):
            # Calculate the minimum path sum for the current cell by considering two possible moves: down and diagonal
            down = triangle[i][j] + front[j]
            diagonal = triangle[i][j] + front[j + 1]
            
            # Store the minimum of the two possible moves in the current row (cur)
            cur[j] = min(down, diagonal)
        
        # Update the previous row (front) with the current row (cur) for the next iteration
        front = cur
        
    # The minimum path sum will be stored in the first element of the front list after the loops
    return front[0]

def main():
    # Define the input triangle and its size
    triangle = [[1], [2, 3], [3, 6, 7], [8, 9, 6, 10]]
    n = len(triangle)
    
    # Call the minimumPathSum function and print the result
    print(minimumPathSum(triangle, n))

if __name__ == '__main__':
    main()


function minimumPathSum(triangle, n) {
  // Initialize two arrays: front and cur
  let front = new Array(n).fill(0);
  let cur = new Array(n).fill(0);

  // Initialize the bottom row of the front array with the values from the triangle
  for (let j = 0; j < n; j++) {
    front[j] = triangle[n - 1][j];
  }

  // Start from the second-to-last row and work upwards
  for (let i = n - 2; i >= 0; i--) {
    for (let j = 0; j <= i; j++) {
      // Calculate the minimum path sum by considering the down and diagonal moves
      const down = triangle[i][j] + front[j];
      const diagonal = triangle[i][j] + front[j + 1];

      // Store the minimum of down and diagonal in the cur array
      cur[j] = Math.min(down, diagonal);
    }
    
    // Update the front array with the values from the cur array
    front = [...cur];
  }

  // The minimum path sum will be stored in the first element of the front array
  return front[0];
}

function main() {
  const triangle = [
    [1],
    [2, 3],
    [3, 6, 7],
    [8, 9, 6, 10]
  ];

  const n = triangle.length;

  console.log(minimumPathSum(triangle, n));
}

// Call the main function to execute the code
main();

Output:14

Complexity Analysis

Time Complexity: O(N*N)

Reason: There are two nested loops

Space Complexity: O(N)

Reason: We are using an external array of size ‘N’ to store only one row.

Video Explanation

Special thanks to Anshuman Sharma and Abhipsita Das for contributing to this article on takeUforward. If you also wish to share your knowledge with the takeUforward fam, please check out this article