Leetcode: Minimum Path Sum

Minimum Path Sum

My Submissions

Total Accepted: 56890 Total Submissions: 170678 Difficulty: Medium

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.

Subscribe to see which companies asked this question

Hide Tags

 Array Dynamic Programming

Show Similar Problems

~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

DP problem, very similar to "Unique path", ONLY difference is that the dp value here we need to choose the minimal one from two possible paths. 

`````````````````````````````````````````````````````````

//codes

class Solution {

public:

    int minPathSum(vector<vector<int>>& grid) {

        //input check 

        if(grid.size()==0)return 0;

        //compose matrix dp and fill the first collom

        int r=grid.size(),c=grid[0].size();

        vector<vector<int>> dp;

        for(int i=0;i<r;i++){

            vector<int> tmp;

            tmp.assign(c, 0);

            dp.push_back(tmp);

            if(i==0)dp[i][0]=grid[0][0];

            else dp[i][0]=grid[i][0]+dp[i-1][0];

        }

        //fill the dp

        for(int i=0;i<r;i++){

            for(int j=1;j<c;j++){

                if(i==0)dp[i][j]= dp[i][j-1]+grid[i][j];

                else dp[i][j]= dp[i][j-1]>dp[i-1][j]?dp[i-1][j]+grid[i][j]:dp[i][j-1]+grid[i][j];

            }

        }

        return dp[r-1][c-1];

    }

};