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.

DP法,以用一个DP[i][j]的数组记录到第[i, j]格的最小值,因为只能从左面和上面转移所以方程为minStep = min { DP[i – 1][j], DP[i][j – 1] },对于i = 0, j = 0的位置肯定是从j – 1, i – 1转移来的所以直接加上grid[i][j]就可以了。最后返回DP[n – 1][m –  1]。

* 观察发现DP数组每个记录只会被使用一次,所以可以把其转变为一维数组DP[j],只记录每一行第j个点的最小值,转移方程为minStep = min { DP[j – 1], DP[j] },这是因为对于每个DP[j],其左侧的点为DP[j – 1],而此时DP[j]记录的是上一行第j个位置的最小值,所以min之后的最小值就是上面和左面的最小值,只需要再加上grid[i][j]就可以得到当前DP[j]的最小值。最后返回DP[j – 1]。算法时间复杂度O(m * n)。

Solution


class Solution {
public:
        int DP[200];
        int minPathSum(vector<vector<int>>& grid) {
                if(grid.size() == 0) return 0;
                if(grid[0].size() == 0) return 0;
                int n = grid.size();
                int m = grid[0].size();
        
                for(int i = 0; i < n; ++i)
                {
                        for(int j = 0; j < m; ++j)
                        {
                                if(j != 0)
                                {
                                        if(i == 0) DP[j] = DP[j - 1];
                                        else DP[j] = min(DP[j - 1], DP[j]);
                                }
                                DP[j] += grid[i][j];
                        }
                }
                return DP[m - 1];
        }
};
28ms

One thought on “64. Minimum Path Sum

Leave a Reply

Your email address will not be published. Required fields are marked *