当前位置: 首页 > article >正文

62.不同路径 63.不同路径ii

题目:62. 不同路径 - 力扣(LeetCode)

思路:此题主要是理清思路,难度不大,注意初始化的是第一行和第一列

代码:

class Solution {
public:
    int uniquePaths(int m, int n) {
    vector<vector<int>> dp(m, vector<int>(n, 0));  
    for(int i = 0;i < m;i++)dp[i][0] = 1;
    for(int i = 0;i < n;i++)dp[0][i] = 1;//初始化
    for(int i = 1;i < m ;i++)
    {
      for(int j = 1;j < n ;j++)  
      {
        dp[i][j] = dp[i-1][j] + dp[i][j-1];
      } 
    }
    return dp[m-1][n-1];
    }
};

题目:63. 不同路径 II - 力扣(LeetCode)

思路:区别在于有障碍就不能走,注意点是在初始化的时候,遇到有障碍后续都走不通要为0,注意循环的跳出条件

 for(int i = 0 ;i < m && obstacleGrid[i][0] == 0; i++)//进行初始化
            dp[i][0] = 1;

第二,在递推公式的前提判断,如果当前位置就是障碍物,直接为跳过。 

代码:

class Solution {
public:
    int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {
        int m = obstacleGrid.size();//行
        int n = obstacleGrid[0].size();//列
        if(obstacleGrid[m-1][n-1] == 1 ||obstacleGrid[0][0] == 1)
        return 0;
        vector<vector<int>>dp(m,vector(n,0));
        for(int i = 0 ;i < m && obstacleGrid[i][0] == 0; i++)//进行初始化
            dp[i][0] = 1;
        for(int j = 0 ;j < n && obstacleGrid[0][j] == 0; j++)//进行初始化
            dp[0][j] = 1;
        for(int i = 1 ;i < m ;i++)
        {
            for(int j = 1 ;j < n ;j++)
            {
                if(obstacleGrid[i][j] == 1)
                continue;
                dp[i][j] = dp[i-1][j] + dp[i][j-1];
            }
        }
        return  dp[m-1][n-1] ;
    }
};


http://www.kler.cn/a/372918.html

相关文章:

  • 02 什么是Babel
  • Apache Hive分布式容错数据仓库系统
  • 2024年AI绘画与写作工具排行榜:提升创作效率必备利器推荐
  • 计算机网络-MSTP概述
  • MySQL 分库分表
  • 使用传感器融合进行3D激光雷达点云运动补偿
  • 我的电脑问题
  • C++设计模式创建型模式———单例模式
  • 计算机网络(Ⅵ)应用层原理
  • HTML入门教程20:HTML头部
  • 代码随想录第十五天
  • oracle和mysql的区别常用的sql语句
  • 模块化CSS
  • 汽车零部件展|2025 第十二届广州国际汽车零部件加工技术及汽车模具展览会邀您共赏汽车行业盛会
  • 使用 Git 命令将本地项目上传到 GitLab
  • JVM 复习1
  • 修改IP分组头部内容的场景
  • 【部署与升级-会议签到的web安装】
  • c++应用网络编程之十三Linux下的epoll模式应用
  • 2D/3D医学图像配准算法
  • MongoDB-Plus
  • web前后端交互方式有哪些?
  • 在manjaro 2024里使用yay命令安装ROS2
  • Linux初阶——线程(Part2):互斥同步问题
  • Nginx 配置基于主机名的 Web 服务器
  • SpringBoot接收LocalDateTime参数