# 2328. Number of Increasing Paths in a Grid
#### Difficulty: Hard
link: https://leetcode.com/problems/number-of-increasing-paths-in-a-grid/

### 1. DFS + DP
#### $O(mn)$ runtime, $O(mn)$ space

DP table紀錄從第i,j個cell出發總共能走幾條路。計算DP[i][j]時，把自己一個cell的path，和自己到周圍鄰居的path，全部加起來。

##### python

class Solution:
    def countPaths(self, grid: List[List[int]]) -> int:
        m, n, mod = len(grid), len(grid[0]), 10 ** 9 + 7
        dp = [[None] * n for _ in range(m)]
        
        def dfs(i, j):
            if dp[i][j] is None:
                dp[i][j] = 1
                for x, y in [[i-1, j], [i+1, j], [i, j-1], [i, j+1]]:
                    if 0 <= x < m and 0 <= y < n and grid[i][j] < grid[x][y]:
                        dp[i][j] = (dp[i][j] + dfs(x, y)) % mod
            return dp[i][j]
        
        total = 0
        for i in range(m):
            for j in range(n):
                total = (total + dfs(i, j)) % mod
        
        return total

###### tags: `leetcode`