seo+网站排名_黄山风景区门票价格_四川百度推广和seo优化_网上店铺的推广方法有哪些

在一个 n x n 的国际象棋棋盘上，一个骑士从单元格 (row, column) 开始，并尝试进行 k 次移动。行和列是 从 0 开始 的，所以左上单元格是 (0,0) ，右下单元格是 (n - 1, n - 1) 。

象棋骑士有8种可能的走法，如下图所示。每次移动在基本方向上是两个单元格，然后在正交方向上是一个单元格。

每次骑士要移动时，它都会随机从8种可能的移动中选择一种(即使棋子会离开棋盘)，然后移动到那里。

骑士继续移动，直到它走了 k 步或离开了棋盘。

返回 骑士在棋盘停止移动后仍留在棋盘上的概率 。

示例 1：

输入: n = 3, k = 2, row = 0, column = 0
输出: 0.0625
解释: 有两步(到(1,2)，(2,1))可以让骑士留在棋盘上。
在每一个位置上，也有两种移动可以让骑士留在棋盘上。
骑士留在棋盘上的总概率是0.0625。

示例 2：

输入: n = 1, k = 0, row = 0, column = 0
输出: 1.00000

提示:

• 1 <= n <= 25
• 0 <= k <= 100
• 0 <= row, column <= n - 1

我的解答

class Solution {public double knightProbability(int n, int k, int row, int column) {// 记录数组：从（i_2,i_3）出发，走完k - i_1步后留在棋盘上的概率double[][][] dfs = new double[k + 1][n][n];return knightProbabilityNum(n,k,row,column,dfs);}// 递归超时,需要优化记忆private double knightProbabilityNum(int n, int k, int row, int column,double[][][] dfs){// 离开了棋盘if( row < 0 || row > n-1 || column < 0 || column > n - 1) return 0;// 步数走完还留在棋盘if(k <= 0 ) return 1;// 之前计算过的if(dfs[k][row][column] > 0) return dfs[k][row][column]; // 八个方向移动double res = knightProbabilityNum(n, k - 1, row - 2, column - 1, dfs) + knightProbabilityNum(n, k - 1, row - 2, column + 1, dfs) + knightProbabilityNum(n, k - 1, row - 1, column - 2, dfs) + knightProbabilityNum(n, k - 1, row - 1, column + 2, dfs) + knightProbabilityNum(n, k - 1, row + 2, column - 1, dfs) + knightProbabilityNum(n, k - 1, row + 2, column + 1, dfs) + knightProbabilityNum(n, k - 1, row + 1, column + 2, dfs) + knightProbabilityNum(n, k - 1, row + 1, column - 2, dfs);/*** 返回从(row,column)出发，走完k步还在旗子上的可能* 如从(x,y)出发，仅走一步:* 八个方向都能留在旗子上，那么dfs[1][x][y] = 1/8 + 1/8....+1/8 = 8*(1/8) = 1;* 如有两个方向不能留在棋盘，那么dfs[1][x][y] = 1/8 + 0/8 + 0/8+....+1/8 = 6*(1/8) = 6/8;       * 如从(x,y)出发，需走两步，那么dfs[2][x][y] = dfs[1][x-2][y-1]/8+..(八个方向)/8..+dfs[1][x+2][x+1]/8*/ return dfs[k][row][column] = res / 8;}
}