参考https://blog.csdn.net/u013300579/article/details/78413647
动态规划，方程为：
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;
}
}
