题目
给你一个 m x n 的整数网格图 grid ，你可以从一个格子移动到 4 个方向相邻的任意一个格子。
请你返回在网格图中从 任意 格子出发，达到 任意 格子，且路径中的数字是 严格递增 的路径数目。由于答案可能会很大，请将结果对 1 0 9 + 7 10^9 + 7109+7 取余 后返回。
如果两条路径中访问过的格子不是完全相同的，那么它们视为两条不同的路径。
示例 1：
输入：grid = [[1,1],[3,4]] 输出：8 解释：严格递增路径包括： - 长度为 1 的路径：[1]，[1]，[3]，[4] 。 - 长度为 2 的路径：[1 -> 3]，[1 -> 4]，[3 -> 4] 。 - 长度为 3 的路径：[1 -> 3 -> 4] 。 路径数目为 4 + 3 + 1 = 8 。
示例 2：
输入：grid = [[1],[2]] 输出：3 解释：严格递增路径包括： - 长度为 1 的路径：[1]，[2] 。 - 长度为 2 的路径：[1 -> 2] 。 路径数目为 2 + 1 = 3 。
解题
方法一：dfs记忆化搜索
通过memory数组保存，每个格点的递增路径数目
比如memory[i][j],表示终点为(i,j)的递增路径数目
class Solution { public: const int MOD=1e9+7; vector<vector<int>> dirs={{-1,0},{0,-1},{1,0},{0,1}}; vector<vector<int>> memory; int dfs(vector<vector<int>>& grid,int i,int j){ if(memory[i][j]>0) return memory[i][j]; memory[i][j]=1; for(vector<int>& dir:dirs){ int nx=i+dir[0]; int ny=j+dir[1]; if(nx<0||nx>=grid.size()||ny<0||ny>=grid[0].size()||grid[i][j]<=grid[nx][ny]) continue; memory[i][j]=(memory[i][j]+dfs(grid,nx,ny))%MOD; } return memory[i][j]; } int countPaths(vector<vector<int>>& grid) { int m=grid.size(); int n=grid[0].size(); memory.resize(m,vector<int>(n)); int res=0; for(int i=0;i<m;i++){ for(int j=0;j<n;j++){ res=(res+dfs(grid,i,j))%MOD; } } return res; } };
方法二：动态规划（超时）
dp[i][j][l]表示格点为(i,j)，路径长度为l的数量，
这样做的目的是因为，只有得到长度为 l-1的路径数量，才能计算出长度为l的路径数量。
缺点：
然而比如 grid[2][3]>grid[2][4]
但是每次都会进行重复比较，遍历到(2,3)，会跟右边比，遍历到(2,4)还要跟左边比，并且没法记忆化，因为dp[i][j][l]只是l长度的结果，只是一个中间值，不是最终结果。
而方法一：是直接保存了每个格点的所有递增路径数目，因此可以记忆化。（dfs，复杂度O ( n 2 ) O(n^2)O(n2)）
方法二可以得到每种路径长度的数量，小量数据可以通过，但是会超时。（矩阵遍历，复杂度O ( n 3 ) O(n^3)O(n3)）
class Solution { public: const int Mod=1e9+7; vector<vector<int>> dirs={{-1,0},{0,-1},{1,0},{0,1}}; int countPaths(vector<vector<int>>& grid) { int res=0; int m=grid.size(); int n=grid[0].size(); int maxPath=m*n; vector<vector<vector<int>>> dp(m,vector<vector<int>>(n,vector<int>(m*n+1))); for(int i=0;i<m;i++){ for(int j=0;j<n;j++){ dp[i][j][0]=0; dp[i][j][1]=1; res++; } } for(int l=2;l<=maxPath;l++){ for(int i=0;i<m;i++){ for(int j=0;j<n;j++){ dp[i][j][l]=0; for(vector<int>& dir:dirs){ int nx=i+dir[0]; int ny=j+dir[1]; if(nx>=0&&nx<m&&ny>=0&&ny<n&&grid[i][j]>grid[nx][ny]){ dp[i][j][l]+=dp[nx][ny][l-1]; } } res=(res+dp[i][j][l])%Mod; } } } return res; } };
