Minimum Path Cost In A Grid - Leetcode Solution

Problem statement

Given a m x n grid containing non-negative integers, find the minimum sum path from top left to bottom right corner.

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

Example 1: 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.

Example 2: Input: grid = [[1,2,3],[4,5,6]] Output: 12

Solution:

We can solve this problem by using dynamic programming. We can create a 2D table dp[][] to store the minimum path sum from grid[0][0] to grid[i][j]. dp[i][j] can be computed as:

dp[i][j] = grid[i][j] + min(dp[i-1][j], dp[i][j-1])

The base cases are:

1. dp[0][0] = grid[0][0]
2. For i = 1 to m-1, dp[i][0] = dp[i-1][0] + grid[i][0] (since we can only move down from top-left corner)
3. For j = 1 to n-1, dp[0][j] = dp[0][j-1] + grid[0][j] (since we can only move right from top-left corner)

Finally, the answer is dp[m-1][n-1].

Code:

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

    dp[0][0] = grid[0][0];
    
    for(int i=1;i<m;i++){
        dp[i][0] = dp[i-1][0] + grid[i][0];
    }
    
    for(int j=1;j<n;j++){
        dp[0][j] = dp[0][j-1] + grid[0][j];
    }
    
    for(int i=1;i<m;i++){
        for(int j=1;j<n;j++){
            dp[i][j] = grid[i][j] + min(dp[i-1][j], dp[i][j-1]);
        }
    }
    
    return dp[m-1][n-1];
}

};

Time Complexity : O(m x n) Space Complexity : O(m x n)

1