出界的路径数（动态规划算法）

算法）"/>

出界的路径数（动态规划算法）

这道题用普通的dfs和bfs要超时，可以用动态规划或者记忆化搜索解决。

//动态规划算法class Solution {
public:int dx[4]={0,0,1,-1};int dy[4]={1,-1,0,0};int countpath=0;int mod=1e9+7;int findPaths(int m, int n, int maxMove, int startRow, int startColumn) {vector<vector<int>>dp(m,vector<int>(n)); //记录到达每个点的道路数量//边界条件：走0步到达起点的道路数量为1；走0步，到达任一点的道路数量为0dp[startRow][startColumn]=1; for(int i=1;i<=maxMove;i++){ //第i步，从第一步开始，最多走maxMove步vector<vector<int>>tmp(m,vector<int>(n)); //记录都第i步后到达每个点的路径数量for(int j=0;j<m;j++){for(int k=0;k<n;k++){int cnt=dp[j][k];if(cnt>0)for(int l=0;l<4;l++){int tx=j+dx[l];int ty=k+dy[l];if(tx>=0&&tx<m&&ty>=0&&ty<n){ //如果没越界就那么走第i部到达该点的道路数量就等于当前数量加上走第i-1步到达该点之前的那一个点的数量tmp[tx][ty]=(tmp[tx][ty]+cnt)%mod; }else{ //如果越界就加到总的出界道路数目中countpath=(countpath+cnt)%mod;}}}}dp=tmp;}return countpath;}
};