# 2328. Number of Increasing Paths in a Grid
###### tags: `Leetcode` `Hard` `DFS+Memorization`
Link: https://leetcode.com/problems/number-of-increasing-paths-in-a-grid/
## 思路
和[0329. Longest Increasing Path in a Matrix](https://hackmd.io/4xn_ebSBSLufvgqkyA_ZcA)很像
我们令dfs(i,j)表示以(i,j)为起点的递增序列的个数。我们可以从任意一个位置(i,j)出发，寻找四周比其大的格子(x,y)，然后递归调用dfs(x,y)，将其结果再加在dfs(i,j)上即可。本题需要记忆化dfs的结果来避免重复调用。
## Code

class Solution {
    public int countPaths(int[][] grid) {
        int m = grid.length, n = grid[0].length;
        int[][] cache = new int[m][n];
        long ans = 0;
        int mod = 1000000007;
        for(int i=0; i<m; i++){
            for(int j=0; j<n; j++){
                ans = (ans+dfs(grid, i, j, cache))%mod;
            }
        }
        return (int)(ans%mod);
    }
    private int dfs(int[][] grid, int x, int y, int[][] cache){
        int m = grid.length, n = grid[0].length;
        if(cache[x][y]!=0) return cache[x][y];
        cache[x][y] = 1;
        int[][] dirs = new int[][]{{-1,0},{1,0},{0,1},{0,-1}};
        long num = 1;
        int mod = 1000000007;
        for(int[] dir:dirs){
            int nextx = x+dir[0], nexty = y+dir[1];
            if(nextx>=0 && nextx<m && nexty>=0 && nexty<n && grid[nextx][nexty]>grid[x][y]){
                num = (num+dfs(grid, nextx, nexty, cache))%mod;
            }
        }
        cache[x][y] = (int)num;
        return cache[x][y];
    }
}