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

Leetcode 不同路径 ||

在这里插入图片描述

算法思想(动态规划 - DP)

这道题属于动态规划(Dynamic Programming,DP)问题,核心思想是利用状态转移方程来计算从起点到终点的不同路径数量,同时考虑障碍物的影响。


1. 问题分析

机器人从左上角 (0,0) 只能向移动,目标是到达右下角 (m-1, n-1)。但路径中可能会有障碍物(值为 1 的格子),机器人不能通过这些格子

我们使用动态规划来记录到达每个位置的路径数,若某个位置有障碍物,则路径数为 0


2. 状态定义

dp[i][j] 表示到达网格 (i, j) 的不同路径数量,则有:

  • 如果 grid[i][j] 是障碍物(值为 1),那么 dp[i][j] = 0(因为无法通行)。

  • 否则,dp[i][j] 的值等于从左边来的路径数 dp[i][j-1] 加上从上边来的路径数 dp[i-1][j]

    [
    dp[i][j] = dp[i-1][j] + dp[i][j-1]
    ]


3. 初始化

  1. 起点 dp[0][0]

    • 如果 grid[0][0] 是障碍物,则机器人无法起步,dp[0][0] = 0,直接返回 0
    • 否则 dp[0][0] = 1,表示机器人只能有一种方式出发。
  2. 第一行(只有向右的可能)

    • 只要当前位置不是障碍物,则 dp[0][j] = dp[0][j-1]
    • 一旦遇到障碍物,之后的格子都无法到达,设为 0
  3. 第一列(只有向下的可能)

    • 只要当前位置不是障碍物,则 dp[i][0] = dp[i-1][0]
    • 同理,遇到障碍物后,后续的 dp[i][0] 设为 0

4. 状态转移

遍历整个网格:

  • grid[i][j] == 1,设 dp[i][j] = 0(无法通行)。
  • 否则计算 dp[i][j] = dp[i-1][j] + dp[i][j-1](来自上方的路径数 + 来自左方的路径数)。

5. 最终结果

dp[m-1][n-1] 存储了到达右下角 (m-1, n-1) 的所有不同路径数,最终返回 dp[m-1][n-1] 作为答案。


6. 复杂度分析

  • 时间复杂度: (O(m \times n)) —— 需要遍历整个 m × n 网格一次。
  • 空间复杂度: (O(m \times n)) —— 需要 dp 数组存储所有格子的信息(可优化为 O(n))。

Java solution :

class Solution {
    public int uniquePathsWithObstacles(int[][] obstacleGrid) {
        //首先获取行和列
        int m = obstacleGrid.length;
        int n = obstacleGrid[0].length;

        //特殊情况判断,如果起点或终点是障碍物,直接返回 0
        if(obstacleGrid[0][0] == 1 || obstacleGrid[m - 1][n - 1] == 1) {
            return 0;
        }
        //然后创建dp数组
        int[][] dp = new int[m][n];

        //初始化起点
        dp[0][0] = 1;

        //初始化第一行
        for(int i = 1; i < n; i++) {
            dp[0][i] = (obstacleGrid[0][i] == 1) ? 0 : dp[0][i - 1];
        }
        //初始化第一列
        for(int j = 1; j < m; j++) {
            dp[j][0] = (obstacleGrid[j][0] == 1) ? 0 : dp[j - 1][0];
        }

        //全局更新dp数组
        for(int i = 1; i < m; i++) {
            for(int j = 1; j < n; j++) {
                if(obstacleGrid[i][j] == 1) {
                    dp[i][j] = 0;
                } else {
                    dp[i][j] = dp[i - 1][j] + dp[i][j - 1]; 
                }
            }
        }
        
        return dp[m - 1][n - 1];
    }
}

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

相关文章:

  • 操作系统相关知识
  • 最短路径--dijkstra
  • Word 小黑第22套
  • 李宏毅NLP-1-课程介绍
  • 新能源汽车IGBT电压平台与SiC器件应用
  • 类和对象的创建
  • Python(1.1)Python实战:一键批量重命名图片文件,告别手动整理!(附完整源码)
  • python调用百度人脸识别接口
  • 【前端面试题】宏任务与微任务的区别
  • C语言之 循环语句:程序运行的核心动力(上)
  • vuex持久化存储,手动保存到localStorage
  • 奥林巴斯道Olympus DAO、奥拉丁模式、诺瓦银行、RWA模型合约解析开发
  • 大数据学习(70)-大数据调度工具对比
  • Navigation页面导航的使用
  • 基于javaweb的SpringBoot校园运动会管理系统设计与实现(源码+文档+部署讲解)
  • 6k ± 1 规则
  • 自然语言处理编程文档
  • 数组题型-二分查找-JS
  • 实战:自适应均衡的设计与实现
  • 【Docker】容器中安装cron命令