參考https://blog.csdn.net/u013300579/article/details/78413647
動(dòng)態(tài)規(guī)劃，方程為：
f[r][c][step] = \sum^{dr, dc} f[r+dr][c+dc][step-1]/8
其中f[r][c][step]表示位置是r，c第step步可能的概率

class Solution {
    public double knightProbability(int N, int K, int r, int c) {
        double[][] d = new double[N][N];
        int[] R = {2,2,-2,-2,1,1,-1,-1};
        int[] C = {1,-1,1,-1,2,-2,2,-2};
        d[r][c] = 1;
        for(int round = 0;round < K;round++){
            double[][] dtemp = new double[N][N];
            for(int i=0;i<N;i++){
                for(int j=0;j<N;j++){
                    for(int a = 0 ;a < 8; a++){
                        int rr = i + R[a];
                        int cc = j + C[a];
                        if(rr >= 0 && rr < N & cc >= 0 && cc < N){
                            dtemp[i][j] += d[rr][cc]/8;
                        }
                    }
                }
            }
            d = dtemp;
        }
        double result = 0; 
        for(int i = 0;i<N;i++){
            for(int j = 0;j<N;j++){
                result += d[i][j];
            }
        }
        return result;
    }
}