Uriel's Corner

Research Associate @ Harvard University / Research Interests: Computer Vision, Biomedical Image Analysis, Machine Learning
posts - 0, comments - 50, trackbacks - 0, articles - 594
从二维格点左上角(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)

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理