Sunday, April 16, 2017

Minimum Path Sum in C++ using tabulation (Dynamic Programming)

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.

class Solution {
public:
    int minPathSum(vector<vector<int>>& grid) {
        int row = grid.size();
        int col = grid[0].size();
        vector<vector<int>> v(row, vector<int>(col,0));
        v[0][0] = grid[0][0];
        for (int i = 1; i< row; i++) 
            v[i][0] = grid[i][0] + v[i-1][0];
        for (int i = 1; i< col; i++) 
            v[0][i] = grid[0][i] + v[0][i-1];
        for (int i = 1; i<row; i++) {
            for (int j = 1; j < col; j++) {
                v[i][j] = grid[i][j] + min (v[i-1][j], v[i][j-1]);
            }
        }
        return v[row-1][col-1];    
    }
};

No comments:

Post a Comment