問一個(gè)二位數(shù)字矩陣中嚴(yán)格遞增的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