Posted on 2023-09-03 16:31
Uriel 閱讀(52)
評論(0) 編輯 收藏 引用 所屬分類:
DP 、
閑來無事重切Leet Code
從二維格點左上角(1,1)開始每次可以向右or向下走，問走到(m,n)一共幾種走法，簡單DP，dp[i][j] = dp[i - 1][j] + dp[i][j - 1]
python2版：
1 #62
2 #Runtime: 10 ms (Beats 90.77%)
3 #Memory: 13.3 MB (Beats 30.67%)
4
5 class Solution(object):
6 def uniquePaths(self, m, n):
7 """
8 :type m: int
9 :type n: int
10 :rtype: int
11 """
12 dp = [[0] * n for _ in range(m)]
13 for i in range(0, m):
14 for j in range(0, n):
15 if i == 0 or j == 0:
16 dp[i][j] = 1
17 else:
18 dp[i][j] = dp[i - 1][j] + dp[i][j - 1]
19 return dp[-1][-1]
python3版，遞歸+lru_cache
1 #62
2 #Runtime: 48 ms (Beats 23.61%)
3 #Memory: 16.5 MB (Beats 11.21%)
4
5 class Solution:
6 def uniquePaths(self, m: int, n: int) -> int:
7 @lru_cache(None)
8 def dp(i, j):
9 if i == 1 or j == 1:
10 return 1
11 return dp(i - 1, j) + dp(i, j - 1)
12 return dp(m, n)