[LeetCode] Minimum Path Sum

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.

Hide Tags

 Array Dynamic Programming

 

思路：和unique path、uique path2 类似，都是动态规划，注意，这里初始值为INT_MAX

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

            vector<int> row(n + 1, INT_MAX);
            vector<vector<int> > f(m + 1, row);

            #if 0
            for(int i = 0; i < m; i ++)
            {
                for(int j = 0; j < n; j ++)
                {
                    cout << grid[i][j] << "	";
                }
                cout << endl;
            }
            cout << endl;
            #endif

            f[1][1] = grid[0][0];
            for(int i = 1; i <= m; i ++)
            {
                for(int j = 1; j <= n; j ++)
                {
                    if(i == 1 && j == 1)
                        continue;
                    f[i][j] = min(f[i-1][j], f[i][j-1]) + grid[i-1][j-1];
                }
            }

            #if 0
            for(int i = 1; i <= m; i ++)
            {
                for(int j = 1; j <= n; j ++)
                {
                    cout << f[i][j] << "	";
                }
                cout << endl;
            }
            #endif

            return f[m][n];

        }
};