首页 > 代码库 > LeetCode Minimum Path Sum

LeetCode Minimum Path Sum

class Solution {public:    int minPathSum(vector<vector<int> > &grid) {        int rows = grid.size();        if (rows < 1) return 0;        int cols = grid[0].size();        if (cols < 1) return 0;                vector<int> pathsum(cols + 1, INT_MAX);        pathsum[0] = 0;                for (int i=0; i<rows; i++) {            for (int j=1; j<=cols; j++) {                int up = pathsum[j];                int left = pathsum[j - 1];                pathsum[j] = grid[i][j - 1];                if (up > left) {                    pathsum[j] += left;                 } else {                    pathsum[j] += up;                }                pathsum[0] = INT_MAX;            }        }        return pathsum[cols];    }};

常规DP,这里使用一个一维的DP数组,作用和二维的一致。