064 - Minimum Path Sum

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

Hide Similar Problems

(M) Unique Paths (H) Dungeon Game

 

典型DP，从右下往左上计算，亦或是从左上往右下计算都可以。

每一步取可以到达该格子的两个相邻格子之间小的那个，加上自己的值即可。

class Solution {
public:
    int minPathSum(vector<vector<int>>& grid) {
        int rst = 0;
        int sz = grid.size();
        if(sz)
        {
            int zz = grid[0].size();
            if(zz)
            {
                for(int ii=sz-1; ii>=0; ii--)
                {
                    for(int jj=zz-1; jj>=0; jj--)
                    {
                        if((jj==zz-1)&&(ii==sz-1))
                            continue;
                        if(jj==zz-1)
                            grid[ii][jj] += grid[ii+1][jj];
                        else if(ii==sz-1)
                            grid[ii][jj] += grid[ii][jj+1];
                        else
                            grid[ii][jj] += min(grid[ii][jj+1], grid[ii+1][jj]);
                    }
                }
                rst = grid[0][0];
            }
        }
        return rst;
    }
};

28 ms.