网站建设怎么分类,网站开发工具 售价,做设计_素材网站有哪,全网推广引流黑科技576. 出界的路径数
给你一个大小为 m x n 的网格和一个球。球的起始坐标为 [startRow, startColumn] 。你可以将球移到在四个方向上相邻的单元格内#xff08;可以穿过网格边界到达网格之外#xff09;。你 最多 可以移动 maxMove 次球。
给你五个整数 m、n、maxMove、star…576. 出界的路径数
给你一个大小为 m x n 的网格和一个球。球的起始坐标为 [startRow, startColumn] 。你可以将球移到在四个方向上相邻的单元格内可以穿过网格边界到达网格之外。你 最多 可以移动 maxMove 次球。
给你五个整数 m、n、maxMove、startRow 以及 startColumn 找出并返回可以将球移出边界的路径数量。因为答案可能非常大返回对 109 7 取余 后的结果。 示例 1 输入m 2, n 2, maxMove 2, startRow 0, startColumn 0 输出6
示例 2
输入m 1, n 3, maxMove 3, startRow 0, startColumn 1 输出12
提示
1 m, n 500 maxMove 500 startRow m0 startColumn n 解题思路
数组定义
数组定义dp[i][j]为到达[i][j]时可能的路径数量因为每一步dp[i][j]的路径数量只和上一步有关因此我们可以用滚动数组的方法来迭代
状态转移
每个格子可以向其他四个方向移动所以需要将当前位置的路径数量累加到周围的4个格子如果移出了边界则累加进入数组
初始化
球的起始坐标为 [startRow, startColumn] 路径数量置为1
代码
class Solution {public int findPaths(int m, int n, int maxMove, int startRow, int startColumn) {int[][] dir {{1, 0}, {0, 1}, {-1, 0}, {0, -1}};int[][] dp new int[m][n];int res0,mod1000000007;dp[startRow][startColumn]1;for (int i0;imaxMove;i){int[][] newDp new int[m][n];for (int k0;km;k)for (int j0;jn;j){int olddp[k][j];if (old0){for (int[] d : dir) {int rd[0]k,cd[1]j;if (r0rmc0cn){newDp[r][c](oldnewDp[r][c])%mod;}else{res(resold)%mod;}}}}dpnewDp;}return res;}
}时间复杂度O(maxMove×m×n)。动态规划需要遍历的状态数是 O(maxMove×m×n)对于每个状态计算后续状态以及出界的路径数的时间都是O(1)。
空间复杂度O(m×n)。使用空间优化的实现空间复杂度是 O(m×n)。
