Minimum Path Sum

PROBLEM

Given a m x n grid filled with non-negative numbers, find a path from top left to bottom right, which minimizes the sum of all numbers along its path.

Note: You can only move either down or right at any point in time.

Example

*Input*: grid = [[1,3,1],[1,5,1],[4,2,1]]
*Output*: 7
Explanation: Because the path 1 → 3 → 1 → 1 → 1 minimizes the sum.

Constraints

m==grid.length
n==grid[i].length
1<=m, n<=200
0<=grid[i][j]<=100

SOLUTION

We’ll use Dynamic Programming method.

First Approach

Steps

First of all we have to return if we are at the end. recursive end
Then get the Right and Bottom neighboor by calling the recursive method with m+1 and n+1 if possible
Then return the actual value of your grid element + the mininum between the right and bottom neighboor

Code

class Solution {
public:
  int minPathSum(vector<vector<int>> &grid) {
    m = grid.size() - 1;
    n = grid[0].size() - 1;
    return dynamicPathSum(grid, 0, 0);
  }

private:
  int m;
  int n;

  int dynamicPathSum(vector<vector<int>> &grid, int r, int c) {
    // Equal to 1e9 to not compromise the min() method
    int right = 1e9;
    int bottom = 1e9;

    // If it's the end of the grid return this value, end of recursive
    if (r == m && c == n)
      return grid[r][c];

    // If there is neighboors, recursive on them
    if (c < n)
      right = dynamicPathSum(grid, r, c + 1);
    if (r < m)
      bottom = dynamicPathSum(grid, r + 1, c);

    // The shortest path is actual value + the mininum between right and bottom neighboor
    return grid[r][c] + min(right, bottom);
  }
};

Conclusion

This code works !! BUT it’s not fast enough !

Second Approach

We keep the same approach or almost.. we’ll use memoization !!

Steps

First of all we have to return if we are at the end. recursive end
Check if in the memo this position is already compute
Then get the Right and Bottom neighboor by calling the recursive method with m+1 if n+1 if possible
Add in the memo the actual value of your grid element + the mininum between the right and bottom neighboor
And Then return the memo value

Code

class Solution {
public:
  int minPathSum(vector<vector<int>> &grid) {
    // Initialize the memo with the good size
    m = grid.size() - 1;
    n = grid[0].size() - 1;
    memo = vector<vector<int>>(m + 1, vector<int>(n + 1));
    return dynamicPathSum(grid, 0, 0);
  }

private:
  // The memo
  vector<vector<int>> memo;

  int n;
  int m;

  int dynamicPathSum(vector<vector<int>> &grid, int r, int c) {
    // Equal to 1e9 to not compromise the min() method
    int right = 1e9;
    int bottom = 1e9;

    // If it's the end of the grid return this value, end of recursive
    if (r == m && c == n)
      return grid[r][c];

    // If position already compute use it
    if (memo[r][c])
      return memo[r][c];

    // If there is neighboors, recursive on them
    if (c < n)
      right = dynamicPathSum(grid, r, c + 1);
    if (r < m)
      bottom = dynamicPathSum(grid, r + 1, c);

    // The shortest path is actual value + the mininum between right and bottom neighboor
    // Add this value to the memo before returning it
    memo[r][c] = grid[r][c] + min(right, bottom);
    return memo[r][c];
  }
};

Conclusion

This code works !! AND it’s much faster !