题目

在一个 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

思路

棋盘上的跳跃走法，一般都是先考虑DFS，但是对于常规的DFS（暴搜）来说，小付去尝试了，结果挺出人意外的，一般这种题是直接就ko的但是今天这道题却超时了。

那如何避免最坏情况的超时呢？前有DFS海洋记忆填平，后有DFS记忆棋盘搜索。如何记忆搜索，根据什么来记忆？我们由题可以知道，马儿最坏的情况就是向四面八方都能跳跃且都不离开棋盘的情况下是最糟糕的，那我们可以设想并且记录，马儿跳过的位置之后在进行跳跃，直到跳不动之前的所有概率之和，作为我们记忆化搜索的缓存记录，在跳跃之前先尝试访问当前点是否访问过并且计算过，如果计算过直接将值返回，并且赋值，反之需要计算并且记录。

解法

class Solution {
    
    //用于记录马儿下一步所跳的方向
    int[][] nextStep = new int[][]{{-1,-2},{-1,2},{1,-2},{1,2},{-2,1},{-2,-1},{2,1},{2,-1}};
    //用于记录马儿跳跃过位置的跳不动之前的所有概率之和
    double memoCache[][][] ;
    public double knightProbability(int n, int k, int row, int column) {
        //初始化缓存结果
        this.memoCache = new double [n][n][k+1];
        //记忆化深搜
        return dfs(n,k,row,column);
    }

    public double dfs(int n,int k ,int row ,int column){
        //递归终止条件之一 只在棋盘中进行递归搜索每个点留在棋盘的概率
       if (row < 0 || row >= n || column < 0 || column >= n)return 0.0;
		//递归终止条件之二 如果跳不动了就该跳出递归
       if (k == 0) return 1.0;
		
        //在进行计算当前点到跳不动之前的所有留在棋盘上的概率之和前对缓存进行查询 如果存在就直接返回结果 减少搜索次数 优化时间复杂度
        if (this.memoCache[row][column][k] != 0.0)return this.memoCache[row][column][k];
        
        //用于记录结果的滚动变量
        double res = 0 ;
        for (int[] step : nextStep){
            //获取下一跳位置的横纵坐标
            int newX = row + step[0];
            int newY = column + step[1];
            //将结果赋值
            res += dfs(n,k-1,newX,newY) / 8.0;
        }
        //记录到缓存中
        this.memoCache[row][column][k] = res;
        return res;
    }
}

总结

• 分析出几种情况，然后分别对各个情况实现