[LeetCode] 63.Unique Paths II
LeetCode II unique paths 63
2023-09-27 14:28:37 时间
A robot is located at the top-left corner of a m x n grid (marked 'Start' in the diagram below).
The robot can only move either down or right at any point in time. The robot is trying to reach the bottom-right corner of the grid (marked 'Finish' in the diagram below).
Now consider if some obstacles are added to the grids. How many unique paths would there be?
An obstacle and empty space is marked as 1
and 0
respectively in the grid.
Note: m and n will be at most 100.
Example 1:
Input: [ [0,0,0], [0,1,0], [0,0,0] ] Output: 2 Explanation: There is one obstacle in the middle of the 3x3 grid above. There are two ways to reach the bottom-right corner: 1. Right -> Right -> Down -> Down 2. Down -> Down -> Right -> Right
62. Unique Paths 的拓展, 有以下不同:
1. 当(i, j)有障碍时dp[i][j] = 0
2. dp[0][j]和dp[i][0]未必为1.
dp[0][j] = obstacleGrid[0][j] ? 0 : dp[0][j-1]
dp[i][0] = obstacleGrid[i][0] ? 0 : dp[i-1][0]
3. 当obstacleGrid [0][0] = 1时,return 0
解法:DP, 建立二维数组,dp[i][j]表示在某一位置能到达的不同路径数量,dp[i][j] = dp[i-1][j] + dp[i][j-1] ,如果某一位置grid[i][j]=1说明为障碍物,那么dp[i][j] = 0,还要注意i, j为0的情况。
Java:
class Solution { public int uniquePathsWithObstacles(int[][] obstacleGrid) { int m = obstacleGrid.length; int n = obstacleGrid[0].length; if (m == 0 || n == 0) { return 0; } if (obstacleGrid[0][0] == 1 || obstacleGrid[m-1][n-1] == 1) { return 0; } int[][] dp = new int[m][n]; dp[0][0] = 1; for(int i = 1; i < n; i++){ if(obstacleGrid[0][i] == 1) { dp[0][i] = 0; } else { dp[0][i] = dp[0][i-1]; } } for(int i = 1; i < m; i++){ if(obstacleGrid[i][0] == 1) { dp[i][0] = 0; } else { dp[i][0] = dp[i-1][0]; } } 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][j-1] + dp[i-1][j]; } } } return dp[m-1][n-1]; } }
Java:
public int uniquePathsWithObstacles(int[][] obstacleGrid) { int width = obstacleGrid[0].length; int[] dp = new int[width]; dp[0] = 1; for (int[] row : obstacleGrid) { for (int j = 0; j < width; j++) { if (row[j] == 1) dp[j] = 0; else if (j > 0) dp[j] += dp[j - 1]; } } return dp[width - 1]; }
Python:
class Solution: def uniquePathsWithObstacles(self, obstacleGrid): mp = obstacleGrid for i in range(len(mp)): for j in range(len(mp[i])): if i == 0 and j == 0: mp[i][j] = 1 - mp[i][j] elif i == 0: if mp[i][j] == 1: mp[i][j] = 0 else: mp[i][j] = mp[i][j - 1] elif j == 0: if mp[i][j] == 1: mp[i][j] = 0 else: mp[i][j] = mp[i - 1][j] else: if mp[i][j] == 1: mp[i][j] = 0 else: mp[i][j] = mp[i - 1][j] + mp[i][j - 1] if mp[-1][-1] > 2147483647: return -1 else: return mp[-1][-1]
Python: wo
class Solution(object): def uniquePathsWithObstacles(self, obstacleGrid): """ :type obstacleGrid: List[List[int]] :rtype: int """ m, n = len(obstacleGrid), len(obstacleGrid[0]) dp = [[0] * n for i in xrange(m)] for i in xrange(m): for j in xrange(n): if obstacleGrid[i][j] == 1: dp[i][j] == 0 else: if i == 0 and j == 0: # 写错成了 or dp[i][j] = 1 elif i == 0: dp[i][j] = dp[i][j-1] elif j == 0: dp[i][j] = dp[i-1][j] else: dp[i][j] = dp[i-1][j] + dp[i][j-1] return dp[-1][-1]
Python: wo
class Solution(object): def uniquePathsWithObstacles(self, obstacleGrid): """ :type obstacleGrid: List[List[int]] :rtype: int """ m, n = len(obstacleGrid), len(obstacleGrid[0]) dp = [[0] * n for i in xrange(m)] for i in xrange(m): for j in xrange(n): if obstacleGrid[i][j] != 1: if i == 0 and j == 0: dp[i][j] = 1 elif i == 0: dp[i][j] = dp[i][j-1] elif j == 0: dp[i][j] = dp[i-1][j] else: dp[i][j] = dp[i-1][j] + dp[i][j-1] return dp[-1][-1]
C++:
class Solution { public: int uniquePathsWithObstacles(vector<vector<int> > &obstacleGrid) { int m = obstacleGrid.size() , n = obstacleGrid[0].size(); vector<vector<int>> dp(m+1,vector<int>(n+1,0)); dp[0][1] = 1; for(int i = 1 ; i <= m ; ++i) for(int j = 1 ; j <= n ; ++j) if(!obstacleGrid[i-1][j-1]) dp[i][j] = dp[i-1][j]+dp[i][j-1]; return dp[m][n]; } };
类似题目:
相关文章
- Leetcode: Longest Substring with At Most K Distinct Characters && Summary: Window做法两种思路总结
- Leetcode: Word Search II
- Leetcode: Find Minimum in Rotated Sorted Array II
- Leetcode: Valid Parentheses
- 【leetcode】14. longest common prefix
- LeetCode高频题55加类似新题45:跳跃游戏 II:最少需要跳多少步才能抵达终点
- [LeetCode] Combination Sum II
- LeetCode常见报错解释
- 203、【栈与队列】leetcode ——剑指 Offer II 040. 矩阵中最大的矩形 / 85. 最大矩形:暴力+单调栈(C++/Pyhont版本)
- 94、【树与二叉树】leetcode ——110. 平衡二叉树(C++版本)
- LeetCode Unique Paths II
- 【LeetCode】210. Course Schedule II
- 【LeetCode】44. Wildcard Matching (2 solutions)
- Leetcode_Wildcard Matching
- [leetCode 75] Sort Colors
- [LeetCode] 1289. Minimum Falling Path Sum II 下降路径最小和之二
- [LeetCode] 1224. Maximum Equal Frequency 最大相等频率
- [LeetCode] 24 Game 二十四点游戏
- [LeetCode] 713. Subarray Product Less Than K 子数组乘积小于K
- [LeetCode] 659. Split Array into Consecutive Subsequences 将数组分割成连续子序列
- [LeetCode] 63. Unique Paths II 不同的路径之二
- [LeetCode] Single Number 单独的数字
- [LeetCode] 67. Add Binary 二进制数相加
- leetcode 126. Word Ladder II 单词接龙 II(困难)