不同路径 II
题目链接: https://leetcode.cn/problems/unique-paths-ii/
解题思路:
设定dp[i][j],代表自[0][0]到[i][j]位置路径数量和
dp[0][0]=1
机器人只能往右或往下走,在无障碍时,dp[i][j]=dp[i-1][j]+dp[i][j-1],在有障碍时,dp[i][j]=0
dp[i][0]和dp[0][j]需要特殊处理
在无障碍时dp[i][0]=dp[i-1][0],dp[0][j]=[0][j-1]
最终遍历dp[n-1][m-1]为最终结果
复杂度分析
时间复杂度: 时间复杂度是 ,其中 是数组
obstacleGrid
的长度 , 是数组obstacleGrid[0]
的长度空间复杂度: 空间复杂度是 ,我们需要一个大小为n*m的数组来保存所有的状态
最后更新于