688. “马”在棋盘上的概率(字节三面)

class Solution {
    Double [][][]memo;
/**
dfs+备忘录
 */
    public double knightProbability(int n, int k, int row, int column) {
         memo=new Double[n+1][n+1][k+1];   
         return dfs(n,k,row,column);
    }

    public double dfs(int n,int k,int i,int j){
        if(i<0||j<0||i>=n||j>=n){
            return 0;
        }
        if(k==0){
            return 1;
        }
        if(memo[i][j][k]!=null){
            return memo[i][j][k];
        }
        double ans=0;
        ans=
        dfs(n,k-1,i-2,j-1)+dfs(n,k-1,i-2,j+1)
        +dfs(n,k-1,i+2,j-1)+dfs(n,k-1,i+2,j+1)
        +dfs(n,k-1,i+1,j-2)+dfs(n,k-1,i-1,j-2)
        +dfs(n,k-1,i+1,j+2)+dfs(n,k-1,i-1,j+2);

        memo[i][j][k]=ans/8;
        return ans/8;//还在棋盘上的数目/可以走的8中可能 
    }
}