Leetcode 63 不同路径 II

2023-12-30 11:25:17

题意理解

????????一个机器人位于一个 m x n 网格的左上角 (起始点在下图中标记为 “Start” )。
机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角(在下图中标记为 “Finish”)。

? ? ? ? 要求:机器人只能往下走和往右走

? ? ? ? 目的:从起始位置走到终点位置

? ? ? ? 特别的:地图中有障碍物,机器人遇到障碍物是过不去的,其可实现的路径就会减少一些。

????????30034a4f2e684e4fb1c17c1bc563a337.png

????????????????

解题思路

? ? ? ? 和没有障碍物的路径记录差不多,唯一的不同之处在于障碍物使可到达的路径减少了。

? ? ? ? 其次还有就是若dp[i,0]或dp[0,j]遇到障碍物时,之后的格子均是不可达的,因为机器人不能往左走或往右走~

? ? ? ? 采用动态规划来解题

? ? ? ? 1.确定dp[i,j]表示起始位置到(i,j)有多少条路径。

? ? ? ? 2.当格子上有障碍物时,dp[i,j]=0

? ? ? ? ? ? 到达格子(i,j)要么从上面下来,要么从左边过去

? ? ? ? ? ? ?则有dp[i,j]=dp[i,0]+dp[0,j]? ?(递推公式)

? ? ? ? 3.初始化:

? ? ? ? ? ? ? ? dp[i,0] dp[0,j]赋值为1,若遇到障碍物,则之后的格子不可达,赋值为0

? ? ? ? 4.根据题意,机器人只能从上往下,或从左往右

? ? ? ? 5.打印dp数组,用于debug,检查其是否符合预期。

1.动态规划解题

 public int uniquePathsWithObstacles(int[][] v) {
        int m=v.length,n=v[0].length;
        //定义存储
        int[][] dp=new int[m][n];
        //初始化-处理障碍1
        for(int i=0;i<m&&v[i][0]!=1;i++) dp[i][0]=1;
        for(int j=0;j<n&&v[0][j]!=1;j++) dp[0][j]=1;
        //遍历
        for(int i=1;i<m;i++){
            for(int j=1;j<n;j++){
                //当前节点有障碍
                if(v[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];
    }

2.分析

时间复杂度:O(m×n) 遍历格子

空间复杂度:O(m×n) 存储动态数组dp

?

文章来源:https://blog.csdn.net/lt_BeiMo/article/details/135277891
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。