Minimum Path Sum

佚名 6年前 (2019-05-14) 随笔 1734人围观抢沙发百度已收录

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.

SRE实战互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。

Example:

Input:
[
  [1,3,1],
  [1,5,1],
  [4,2,1]
]
Output: 7
Explanation: Because the path 1→3→1→1→1 minimizes the sum.

recursion

class Solution
{
public:
    int minPathSum(vector<vector<int>>& grid)
    {
        if(grid.empty())
            return 0;
        vector<int> res;
        int sum=grid.at(0).at(0);
        minPathSum(grid,0,0,sum,res);
        return *min_element(res.begin(),res.end());
    }
private:
    void minPathSum(vector<vector<int>>& grid,int x,int y,int &sum,vector<int> &res)
    {
        if(x==grid.size()-1&&y==grid.at(0).size()-1)
        {
            res.push_back(sum);
            return ;
        }

        if(x+1<grid.size())
        {
            sum+=grid.at(x+1).at(y);
            minPathSum(grid,x+1,y,sum,res);
            sum-=grid.at(x+1).at(y);
        }
        if(y+1<grid.at(0).size())
        {
            sum+=grid.at(x).at(y+1);
            minPathSum(grid,x,y+1,sum,res);
            sum-=grid.at(x).at(y+1);
        }
        return ;
    }
};

class Solution
{
public:
    int minPathSum(vector<vector<int>>& grid)
    {
        if(grid.empty())
            return 0;

        int row=grid.size();
        int col=grid.at(0).size();
        vector<vector<int>> tmp(grid);

        for(int i=1;i<row;++i)
            tmp.at(i).at(0)+=tmp.at(i-1).at(0);
        for(int i=1;i<col;++i)
            tmp.at(0).at(i)+=tmp.at(0).at(i-1);

        for(int i=1;i<row;++i)
        {
            for(int j=1;j<col;++j)
                tmp.at(i).at(j)+=min(tmp.at(i-1).at(j),tmp.at(i).at(j-1));
        }

        return tmp.at(row-1).at(col-1);
    }
};