LC-62/63/64不同路径

LC62题目

一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为“Start” ）。

机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为“Finish”）。

问总共有多少条不同的路径？

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/unique-paths
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

题解

这个很好想，公式d[m,n]=d[m-1,n]+d[m,n-1];

//第一种解法 超时
class Solution {
public:
    int uniquePaths(int m, int n) {
        //d[m,n]=d[m-1,n]+d[m,n-1];
        int res=0;
        if(m>1&&n>1)
            res=uniquePaths(m-1,n)+uniquePaths(m,n-1);
        else
            res=1;
        return res;
        
        
    }
};

因为超时，我就找了个数组记录计算结果，AC后的结果
这里传二维数组失败，又传了vector

class Solution {
public:
    // int tmp1=0;
    // int tmp2;
    void count(vector< vector<int> > &rec,int m,int n,int a,int b){
        int res=0;
        if(m>1&&n>1){
            if(rec[m-1][n]==0){
                count(rec,m-1,n,a,b);
                if(m-1<=b&&n<=a){
                    rec[n][m-1]=rec[m-1][n];
                }
            }
            if(rec[m][n-1]==0){
                count(rec,m,n-1,a,b);
                if(n-1<=a&&m<=b){
                    rec[n-1][m]=rec[m][n-1];
                }
            }
           rec[m][n]=rec[m-1][n]+rec[m][n-1];
        }
        else{            
            rec[m][n]=1;            
        }
        
    }
    int uniquePaths(int m, int n) {
        //d[m,n]=d[m-1,n]+d[m,n-1];
        vector< vector<int> > rec;
        for(int i=0;i<m+1;i++){
            vector<int> tmpr;

            for(int j=0;j<n+1;j++){
                tmpr.push_back(0);
            }
            rec.push_back(tmpr);
        }
         count(rec,m,n,m,n);
        
        return rec[m][n];
        
        
    }
};

实际上，直接填数组就可以了TAT
但是动态规划还是注意一下填数组的顺序，这里用的都是填过的数，有的时候用的不一定是填过的数字

  int uniquePaths(int m, int n) {
        //d[m,n]=d[m-1,n]+d[m,n-1];
        int rec[m][n];
        for(int i=0;i<m;i++){
            for(int j=0;j<n;j++){
                if(i==0||j==0){
                    rec[i][j]=1;
                }else{
                    rec[i][j]=rec[i-1][j]+rec[i][j-1];
                }
            }
        }
        return rec[m-1][n-1];
        
        // return rec[m][n];
        
        
    }

LC63题目

一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为“Start” ）。

机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为“Finish”）。

现在考虑网格中有障碍物。那么从左上角到右下角将会有多少条不同的路径？

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/unique-paths-ii
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

题解

class Solution {
public:
    int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {
        //差不多，看是否有1.
        int a=obstacleGrid.size();
        int b=obstacleGrid[0].size();
        if(obstacleGrid[a-1][b-1]==1){
            return 0;
        }
        int k=-1;
        long long rec[a][b];
        memset(rec,0,sizeof(rec));
        for(int i=0;i<a;i++){
            for(int j=0;j<b;j++){
                if(obstacleGrid[i][j]==1){
                    rec[i][j]=0;
                }else if(i==0||j==0){
                   // 看路中是不是有1                    
                   if(i==0&&j>0){
                       rec[i][j]=rec[i][j-1];
                   }
                   else if(j==0&&i>0){
                       rec[i][j]=rec[i-1][j];
                   }else {
                       rec[i][j]=1;
                   } 
                    
                }else{
                    rec[i][j]=rec[i-1][j]+rec[i][j-1];
                }
            }
        }
        return rec[a-1][b-1];
        
    }
};

以上这种必须把返回数组定义为long类型，否则中间值会产生int溢出

另一种（我看有js这样写的，但是C++写就超时）

    int count(vector<vector<int>>& obstacleGrid,int i,int j){
        int res=0;
        if(obstacleGrid[i][j]==1)
            return res;
        else if(i==0||j==0){
                 if(i==0&&j>0){
                       res=count(obstacleGrid,i,j-1);
                   }
                   else if(j==0&&i>0){
                       res=count(obstacleGrid,i-1,j);
                   }else {
                       res=1;
                   } 
        }else{
            res=count(obstacleGrid,i,j-1)+count(obstacleGrid,i-1,j);
        }
        return res;
    }
    
    int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {
        
        
        
        //差不多，看是否有1.
        int a=obstacleGrid.size();
        int b=obstacleGrid[0].size();
        int res=count(obstacleGrid,a-1,b-1);
      return res;
}

题目LC64

LC63稍微改一下可做LC64的题解

给定一个包含非负整数的 m x n 网格，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。

说明：每次只能向下或者向右移动一步。

示例:

输入:
[
  [1,3,1],
  [1,5,1],
  [4,2,1]
]
输出: 7
解释: 因为路径 1→3→1→1→1 的总和最小。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/minimum-path-sum
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

class Solution {
public:
    int minPathSum(vector<vector<int>>& grid) {
                //差不多，看是否有1.
        int a=grid.size();
        int b=grid[0].size();
        long long rec[a][b];//记录结果
        memset(rec,0,sizeof(rec));
        for(int i=0;i<a;i++){
            for(int j=0;j<b;j++){
                if(i==0||j==0){
                   // 看路中是不是有1                    
                   if(i==0&&j>0){
                       rec[i][j]=rec[i][j-1]+grid[i][j];
                   }
                   else if(j==0&&i>0){
                       rec[i][j]=rec[i-1][j]+grid[i][j];
                   }else {
                       rec[i][j]=grid[i][j];
                   } 
                    
                }else{
                    if(rec[i-1][j]>rec[i][j-1])
                        rec[i][j]=rec[i][j-1]+grid[i][j];
                    else
                        rec[i][j]=rec[i-1][j]+grid[i][j];
                }
            }
        }
        return rec[a-1][b-1];
    }
};