Leetcode 63 不同路径 II

题意理解：

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

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

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

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

????????

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

解题思路：

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

? ? ? ? 其次还有就是若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

?