0064_Minimum_Path_Sum.cpp

#include<iostream>
#include<string>
#include<vector>

using namespace std;

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

        // bound
        dp[0][0] = grid[0][0];
        for(i = 1; i < m; i++) dp[i][0] = grid[i][0] + dp[i-1][0];
        for(j = 1; j < n; j++) dp[0][j] = grid[0][j] + dp[0][j-1];

        for(i = 1; i < m; i++){
            for(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];
    }
};

int main(){
    Solution solve;
    vector<vector<int> > input = {{1,3,1},{1,5,1},{4,2,1}};
    //vector<vector<int> > input = {{1,0}};
    
    cout << "Input: " << endl;
    for(int i = 0; i < input.size(); i++){
        for(int j = 0; j < input[i].size(); j++)
            cout << input[i][j] << " ";
        cout << endl;
    }

    cout << "Output: " << solve.minPathSum(input) << endl;
        
    return 0;
}