LeetCode 솔루션 분류
[5/20] 63. Unique Paths II
본문
[LeetCode 시즌 3] 2022년 5월 20일 문제입니다.
https://leetcode.com/problems/unique-paths-ii/
63. Unique Paths II
Medium
4748378Add to ListShareYou are given an m x n integer array grid. There is a robot initially located at the top-left corner (i.e., grid[0][0]). The robot tries to move to the bottom-right corner (i.e., grid[m-1][n-1]). The robot can only move either down or right at any point in time.
An obstacle and space are marked as 1 or 0 respectively in grid. A path that the robot takes cannot include any square that is an obstacle.
Return the number of possible unique paths that the robot can take to reach the bottom-right corner.
The testcases are generated so that the answer will be less than or equal to 2 * 109.
Example 1:
Input: obstacleGrid = [[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
Example 2:
Input: obstacleGrid = [[0,1],[0,0]] Output: 1
Constraints:
m == obstacleGrid.lengthn == obstacleGrid[i].length1 <= m, n <= 100obstacleGrid[i][j]is0or1.
관련자료
-
링크
댓글 2
mingki님의 댓글
- 익명
- 작성일
C++
Runtime: 2 ms, faster than 81.84% of C++ online submissions for Unique Paths II.
Memory Usage: 8 MB, less than 13.17% of C++ online submissions for Unique Paths II.
Runtime: 2 ms, faster than 81.84% of C++ online submissions for Unique Paths II.
Memory Usage: 8 MB, less than 13.17% of C++ online submissions for Unique Paths II.
class Solution {
public:
int uniquePathsWithObstacles(vector<vector<int>>& grid) {
int n = grid.size();
int m = grid[0].size();
vector<vector<int>> dp(n + 1, vector<int>(m + 1, 1));
for (int i = 1; i <= n; ++i) {
dp[i][1] = grid[i - 1][0] == 1 ? 0 : dp[i - 1][1];
}
for (int j = 1; j <= m; ++j) {
dp[1][j] = grid[0][j - 1] == 1 ? 0 : dp[1][j - 1];
}
for (int i = 2; i <= n; ++i) {
for (int j = 2; j <= m; ++j) {
if (grid[i - 1][j - 1] == 0) {
dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
}
else {
dp[i][j] = 0;
}
}
}
return dp[n][m];
}
};coderoncruise님의 댓글
- 익명
- 작성일
dynamic programming
class Solution:
def uniquePathsWithObstacles(self, obstacleGrid: List[List[int]]) -> int:
if obstacleGrid[0][0] == 1 or obstacleGrid[-1][-1] == 1:
return 0
rows = len(obstacleGrid)
cols = len(obstacleGrid[0])
board = [[0] * cols for _ in range(rows)]
for c in range(cols - 1, -1, -1):
if obstacleGrid[-1][c] == 1:
break
board[-1][c] = 1
for r in range(rows - 1, -1 ,-1):
if obstacleGrid[r][-1] == 1:
break
board[r][-1] = 1
print(board)
for r in range(rows - 2, -1, -1):
for c in range(cols - 2, -1, -1):
if obstacleGrid[r][c] == 1:
continue
board[r][c] = board[r+1][c] + board[r][c+1]
return board[0][0]
