[Leetcode] 62. Unique Paths
11305 ワード
問題のショートカット
Combination
Time Complexity: O(min(m, n))
Space Complexity: O(1)
Bottom up
Time Complexity: O(mn)
Space Complexity: O(mn)
Time Complexity: O(mn)
Space Complexity: O(mn)
Combination
Time Complexity: O(min(m, n))
Space Complexity: O(1)
class Solution:
def uniquePaths(self, m: int, n: int) -> int:
# combination: pick min(m-1, n-1) steps from total steps\
total = m + n - 2
smaller = min(m, n) - 1
denominator, numerator = 1, 1 # 분모, 분자
for i in range(smaller):
denominator *= total - i
numerator *= i + 1
return denominator // numerator
Dynamic ProgrammingBottom up
Time Complexity: O(mn)
Space Complexity: O(mn)
class Solution:
def uniquePaths(self, m: int, n: int) -> int:
memo = [[0 for _ in range(n)] for _ in range(m)]
for r in range(m):
memo[r][0] = 1
for c in range(n):
memo[0][c] = 1
for r in range(1, m):
for c in range(1, n):
memo[r][c] = memo[r-1][c] + memo[r][c-1]
return memo[-1][-1]
Top downTime Complexity: O(mn)
Space Complexity: O(mn)
class Solution:
def uniquePaths(self, m: int, n: int) -> int:
memo = [[0 for _ in range(n)] for _ in range(m)]
for r in range(m):
memo[r][0] = 1
for c in range(n):
memo[0][c] = 1
def findPaths(m: int, n: int) -> int:
if not memo[m][n]:
memo[m][n] = findPaths(m-1, n) + findPaths(m, n-1)
return memo[m][n]
return findPaths(m-1, n-1)
Reference
この問題について([Leetcode] 62. Unique Paths), 我々は、より多くの情報をここで見つけました https://velog.io/@haebin/Leetcode-62.-Unique-Pathsテキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol