Minimum Path Sum

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.

Output Format

Return a single integer denoting the minimum sum of a path from cell (1, 1) to cell (M, N).

Example Input

 A = [  [1, 3, 2]
        [4, 3, 1]
        [5, 6, 1]
     ]

Example Output

 9

Example Explanation

 The path is 1 -> 3 -> 2 -> 1 -> 1
 So ( 1 + 3 + 2 + 1 + 1) = 8

Constraints:

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

Algorithm

We 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));
class Solution {
    public int minPathSum(int[][] grid) {
        
        if(grid == null || grid.length == 0){
            return 0;
        }
        int m = grid.length;
        int n = grid[0].length;
        int[][] dp = new int[m][n];
        dp[0][0] = grid[0][0];
        
        for(int i = 1 ; i < n ; i++){
            dp[0][i] = grid[0][i] + dp[0][i-1];
        }
        
        for(int i = 1 ; i < m ; i++){
            dp[i][0] = grid[i][0] + dp[i-1][0];
        }
        
        for(int i = 1 ; i < m ; i++){
            for(int j = 1 ; j < n ; j++){
                dp[i][j] = grid[i][j] + Math.min(dp[i][j-1], dp[i-1][j]);
            }
        }
        return dp[m-1][n-1];
    }
}

Complexity Analysis

  • Time Complexity : O(mn). We traverse the entire matrix once.
  • Space Complexity : O(mn). Another matrix of the same size is used.

Categories: Dynamic Programming

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s