力扣算法篇：出界的路径数

算法篇：出界的路径数"/>

力扣算法篇：出界的路径数

题解：
动态规划五部曲：
1、确定dp数组及其下标含义
dp[i][j][k]表示球移动i次之后位于坐标(j,k)的路径数，由题意i从0到maxmove遍历，累加出界的路径数即可
2、确定递推式
球移动了i次之后位于坐标(j,k),（不出界且i小于maxmove的情况下）则移动i+1次之后，球必定位于与坐标(j,k)相邻的一个坐标（j1,k1），如果此时球出界了 则将dp[i][j][k]的值加到出界的路径数，否则 将dp[i][j][k]的值加入到dp[i+1][j1][k1]

//实际情况要求余
if(出界){count+=dp[i][j][k];
}else{dp[i+1][j1][k1]+=dp[i][j][k];
}

3、初始化

//移动0次到起始位置的路径数为1
dp[0][startRow][startColumn] = 1；
//移动0次到非起始位置的路径数为0
dp[0][j][k] = 0;

4、确定遍历顺序
从移动次数为0到maxmove,从上到下，从左到右，
5、举例推导dp
暂不做推导

class Solution {
public://求余数static constexpr int MOD = 1'000'000'007;int findPaths(int m, int n, int maxMove, int startRow, int startColumn) {//移动方向 上下左右 二维数组vector<vector<int>>  directions = {{-1,0},{1,0},{0,-1},{0,1}};//出界路径数int outCounts = 0;//dp数组 三维vector<vector<vector<int>>> dp(maxMove+1,vector<vector<int>>(m,vector<int>(n,0)));//初始化dp[0][startRow][startColumn] = 1;//计算dp数组 累加每个i的出界路径数 i在最外面 然后从上到下 从左到右for(int i = 0;i<maxMove;i++){for(int j = 0;j<m;j++){for(int k = 0;k<n;k++){int count = dp[i][j][k];//第一次进入 起始点if(count>0){//移动for(auto &direction:directions){//移动点int j1 = j + direction[0];int k1 = k + direction[1];//判断是否出界if(j1>=0 && j1<m && k1>=0 && k1<n){//未出界dp[i+1][j1][k1] = (dp[i+1][j1][k1]+count)%MOD;}else{//出界 加入出界路径数outCounts = (outCounts+count)%MOD;}}}}}}return outCounts;}
};