2022-02-17

先用暴力递归写，结果堆栈溢出了，接着依据暴力递归可以转动态规划。用dp作缓存，存状态，
没注意int除去的时候会自动取整，最后改成了double类型。
java版本：

class Solution {
      public static int[][] dirs = {{-2, -1}, {-1, -2}, {-1, 2}, {-2, 1},
      {1,-2},{2,-1},{1,2},{2,1}};
      int count=0;
    //   计算所有的
    public double knightProbability(int n, int k, int row, int column) {
    //所有的可能性 8*k;

        // 统计所有的情况的终止坐标
        // 进行判断是否还留在棋盘上
        // 边界是 0，n-1
        // 暴力递归转动态规划
        double[][][] dp=new double[k+1][n][n];
        int ni,nj;
        
       
        for(int m=0;m<=k;m++){
        for(int i=0;i<n;i++){
            for(int j=0;j<n;j++){
                if(m==0){
                    dp[m][i][j]=1;
                    
                   
                }else{

             
                for(int nl=0;nl<dirs.length;nl++){
                    ni=dirs[nl][0]+i;
                    nj=dirs[nl][1]+j;
                    if(ni>=0 && ni<n && nj>=0 && nj<n ){
                     dp[m][i][j]+=dp[m-1][ni][nj]/8;
                    }

                }
                }
                
            }
           }
        }

    
        return dp[k][row][column];
    
    }

 }