Posted on 2023-09-03 16:31
Uriel 阅读(40)
评论(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)