Uriel's Corner

Research Associate @ Harvard University / Research Interests: Computer Vision, Biomedical Image Analysis, Machine Learning
posts - 0, comments - 50, trackbacks - 0, articles - 594
问一个二位数字矩阵中严格递增的path有几条(可以往上下左右走),DP+递归+Memorization
参考了Discussion-> https://leetcode.com/problems/number-of-increasing-paths-in-a-grid/solutions/3650130/python3-solution/


 1 #2328
 2 #Runtime: 2652 ms (Beats 28.65%)
 3 #Memory: 78.9 MB (Beats 49.52%)
 4 
 5 class Solution:
 6     def countPaths(self, grid: List[List[int]]) -> int:
 7         MOD = 10 ** 9 + 7
 8         n, m = len(grid), len(grid[0])
 9         dp = [[-1 for _ in range(m)] for _ in range(n)]
10 
11         def cal(r, c, pre):
12             nonlocal n, m
13             if r < 0 or c < 0 or r >= n or c >= m or grid[r][c] <= pre:
14                 return 0
15             if dp[r][c] != -1:
16                 return dp[r][c]
17             dir = [[1, 0], [-1, 0], [0, -1], [0, 1]]
18             t = 1
19             for d in dir:
20                 tr = r + d[0]
21                 tc = c + d[1]
22                 t += cal(tr, tc, grid[r][c])
23             dp[r][c] = t
24             return t
25         
26         ans = 0
27         for r in range(n):
28             for c in range(m):
29                 ans = (ans + cal(r, c, -1)) % MOD
30         return ans

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