【Leetcode】64. Minimum Path Sum（动态规划）

「爱情、让人受尽委屈。」 2022-02-27 13:34 137阅读 0赞

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.

**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.

题目大意：

给出矩阵，计算所需要代价最小的一条路径，从左上走到左下。规定只能向左并向下走。

解题思路：

一定要把题目读完，第一次超时发现规定了两个方向。。。。。与前面询问有多少条路径可以从左上到右下相似，此时我们需要将第一行第一列使用叠加的方式进行初始化，因为能够到达此处的位置只有他上面或左边的。再初始好第一行和第一列之后，我们可以计算中间的值，计算方式为本位置的值加上，通过计算得出的上面和左面中的最小值。

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

顺便贴一下四个方向的搜索代码，超时的教训。

class Solution {
    private:
    	int n,m;
    	int ans = -1;
    	int xx[4] = {0,0,1,-1};
    	int yy[4] = {-1,1,0,0};
    	vector<vector<int>> map_g;
    	bool valid(int x, int y, int tmp, vector<vector<int> > g){
    		
    		if(x>=0&&x<n&&y>=0&&y<m){
    			if((tmp + g[x][y] <= ans || ans == -1) && map_g[x][y]==0){
    				return true;
    			}
    		}
    		return false;
    	}
    	void dfs(int x, int y , int tmp, vector<vector<int> > g){
    		if (x == n-1 && y == m-1){
    			if(ans == -1){
    				ans = tmp;
    			}else{
    				if (ans> tmp){
    					ans = tmp;
    				}
    			}
    			return;
    		}
    		for(int i=0;i<4;i++){
    			
    			int cor_x = x + xx[i];
    			int cor_y = y + yy[i];
    			
    			if(valid(cor_x, cor_y, tmp, g)){
    				map_g[cor_x][cor_y] = 1;
    				dfs(cor_x,cor_y, tmp + g[cor_x][cor_y], g);
    				map_g[cor_x][cor_y] = 0;
    			}
    		}
    	}
    	
    public:
        int minPathSum(vector<vector<int>>& grid) {
            n = grid.size();
            m = grid[0].size();
            for(int i=0;i<n;i++){
            	vector<int> t;
            	for(int j=0;j<m;j++){
            		t.push_back(0);
    			}
    			map_g.push_back(t);
    		}
    		map_g[0][0] = 1;
            dfs(0, 0, grid[0][0], grid);
            return ans;
        }
    };