Problem description:
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.

1
2
3
4
5
6
7
8
9
10
Example:

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

Solution:

  1. 2D array DP
    Use an extra matrix dp of the same size as the original matrix. In this matrix, dp(i, j) represents the minimum sum of the path from the index (i, j) to the bottom rightmost element. We start by initializing the bottom rightmost element of dp as the last element of the given matrix. Then for each element starting from the bottom right, we traverse backwards and fill in the matrix with the required minimum sums. Now, we need to note that at every element, we can move either rightwards or downwards. Therefore, for filling in the minimum sum, we use the equation:

dp(i,j)=grid(i,j)+min(dp(i+1,j),dp(i,j+1))

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    int minPathSum(vector<vector<int>>& grid) {
        auto& s = grid;
        int n = grid.size();
        int m = grid[0].size();
        for(int i = n-1; i>=0; --i){
            for(int j = m-1; j>=0; --j){
                if(i == n-1 && j != m-1)    //edge case, last row
                    s[i][j] += s[i][j+1];
                else if(i != n-1 && j == m-1)
                    s[i][j] += s[i+1][j];
                else if(i != n-1 && j != m-1)
                    s[i][j] = s[i][j] + min(s[i][j+1], s[i+1][j]);
            }          
        }
        return s[0][0];
    }    
};

time complexity: O(mn)
space complexity: O(mn)

  1. 1D array
    We can do the same work using a dp array of the row size, since for making the current entry all we need is the dp entry for the bottom and the right element. Thus, we start by initializing only the last element of the array as the last element of the given matrix. The last entry is the bottom rightmost element of the given matrix. Then, we start moving towards the left and update the entry dp(j) as:

dp(j)=grid(i,j)+min(dp(j),dp(j+1))

We repeat the same process for every row as we move upwards. At the end dp(0)dp(0) gives the required minimum sum.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
    int minPathSum(vector<vector<int>>& grid) {
        int n = grid.size(), m= grid[0].size();
        vector<int> dp(m, 0);
        for(int i= n-1; i>= 0; --i){
            for(int j = m-1; j>= 0; --j){
                if(i == n-1 && j != m-1) dp[j] = grid[i][j]+ dp[j+1];
                else if(i != n-1 && j == m-1) dp[j] = grid[i][j]+ dp[j];
                else if(i != n-1 && j != m-1) dp[j] = grid[i][j] + min(dp[j], dp[j+1]);
                else dp[j] = grid[i][j];
                    
            }
        }
        return dp[0];
    }
};

time complexity: O(mn)
space complexity: O(n)