Question Decoration:

• Consider the matrix as a rectangular plot, and grids as houses
• Now, you have to go from top-left house to bottom right house
• Also when you are in some house, you have to pay the rent
• You can move by only one house at a time, either to Right house or to Down house
• You have to find the minimum rent to reach the bottom-Right house

Solution:

• Dynamic Programming(DP)

• BECAUSE this problem requires optimizing the rent(minimum rent),and at each step we have multiple options, therefore we will use DP steps:

  • Create a dp array of same size as grid
  • dp[0][0] = grid[0][0] , b’coz we are initially in this house
  • dp[i][j] means minimum rent i need to pay to reach the house [i,j]
  • for 0-th row , there is only one way to reach any house, and that is by moving to right, therefore , dp[0][i] = dp[0][i-1] + grid[0][i] (rent paid so far + rent for this house)
  • for 0th column, there is only one way to reach any house, and that is by moving down, therefore, dp[i][0] = dp[i-1][0] + grid[i][0] (rent paid so far + rent for this house)
  • And now for rest of the houses in the grid, say grid[i][j]
    • we can reach either from grid[i-1][j]
    • or from grid[i][j-1]
    • we will choose the one with minimum rent
    • therefore, dp[i][j] = min(dp[i-1][j],dp[i][j-1]) + grid[i][j]

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,0)); // m 행의 n 열 with value 0
    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] = min(dp[i-1][j],dp[i][j-1]) + grid[i][j];
    return dp[m-1][n-1];
    }
};