LeetCode 솔루션 분류
[8/1] 62. Unique Paths
본문
Medium
10250319Add to ListShareThere is a robot on an m x n
grid. The robot is 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.
Given the two integers m
and n
, return the number of possible unique paths that the robot can take to reach the bottom-right corner.
The test cases are generated so that the answer will be less than or equal to 2 * 109
.
Example 1:
Input: m = 3, n = 7 Output: 28
Example 2:
Input: m = 3, n = 2 Output: 3 Explanation: From the top-left corner, there are a total of 3 ways to reach the bottom-right corner: 1. Right -> Down -> Down 2. Down -> Down -> Right 3. Down -> Right -> Down
Constraints:
1 <= m, n <= 100
Accepted
1,048,365
Submissions
1,717,680
관련자료
댓글 2
학부유학생님의 댓글
- 익명
- 작성일
Runtime: 34 ms, faster than 90.49% of Python3 online submissions for Unique Paths.
Memory Usage: 13.9 MB, less than 73.91% of Python3 online submissions for Unique Paths.
Memory Usage: 13.9 MB, less than 73.91% of Python3 online submissions for Unique Paths.
class Solution:
def uniquePaths(self, m: int, n: int) -> int:
prev_path = [1]*n
next_path = []
i = 1
while i < m:
for j in range(n):
from_top = prev_path[j]
from_left = next_path[j-1] if j > 0 else 0
next_path.append(from_top + from_left)
prev_path = next_path
next_path = []
i += 1
return prev_path[n-1]
mingki님의 댓글
- 익명
- 작성일
C++
Runtime: 0 ms, faster than 100.00% of C++ online submissions for Unique Paths.
Memory Usage: 6.4 MB, less than 53.20% of C++ online submissions for Unique Paths.
Runtime: 0 ms, faster than 100.00% of C++ online submissions for Unique Paths.
Memory Usage: 6.4 MB, less than 53.20% of C++ online submissions for Unique Paths.
class Solution {
public:
int uniquePaths(int m, int n) {
vector<vector<int>> dp(m + 1, vector<int>(n + 1, 0));
for (int i = 0; i < m; ++i) {
dp[i][0] = 1;
}
for (int j = 0; j < n; ++j) {
dp[0][j] = 1;
}
for (int i = 1; i < m; ++i) {
for (int j = 1; j < n; ++j) {
dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
}
}
return dp[m - 1][n - 1];
}
};