首页 > 代码库 > 【LeetCode】【Python】Minimum Path Sum

【LeetCode】【Python】Minimum Path Sum

此题不难,可以用dfs来做,也可以用动态规划,但明显dfs性能不如dp。

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.

动态规划:

用dis[x][y]表示到达(x,y)的最短距离,因为只能向右和向下,所以dis(x,y) = dis[x-1][y]和dis[x][y-1]的较小值加上A(x,y)即可。最终所求转化为dis(m-1,n-1)

class Solution {
public:
    int minPathSum(vector<vector<int> > &grid) {
        int mm=grid.size();
        int nn=grid[0].size();
        vector<vector<int> > dis;
        vector<int> vec;
        vec.push_back(grid[0][0]);
        for (int i=1;i<nn;i++){
            vec.push_back(vec[i-1]+grid[0][i]);
        }
        dis.push_back(vec);
        for (int i=1;i<mm;i++){
            vec.clear();
            for (int j=0;j<nn;j++){
                if (j==0)   vec.push_back(dis[i-1][j]+grid[i][j]);
                else    vec.push_back(min(dis[i-1][j],vec[j-1])+grid[i][j]);
            }
            dis.push_back(vec);
        }
        return dis[mm-1][nn-1];
    }
};

除此,还应注意很多细节,几次提交都不能通过就是因为没处理好vec和dis的关系。好久没用c++做题,vector还没有push值的时候是不能通过直接访问下标进行赋值的,这一点需要特别注意。

【LeetCode】【Python】Minimum Path Sum