688. Knight Probability in Chess

解题思路：

1. 对于每一步（总步数：K）更新一次dp0[i][j]
2. 当符合条件时：dp1[i][j] += dp[row][col]

代码：

class Solution {
int[][] moves = {{1, 2}, {1, -2}, {2, 1}, {2, -1}, {-1, 2}, {-1, -2}, {-2, 1}, {-2, -1}};
public double knightProbability(int N, int K, int r, int c) {

    int len = N;
    double[][] dp0 = new double[len][len];
    for(double[] row : dp0) Arrays.fill(row, 1);
    for(int l = 0; l < K; l++){
        double[][] dp1 = new double[len][len];
        for(int i = 0; i < len; i++){
            for(int j = 0; j < len; j++){
                for(int[] move : moves){
                    int row = i + move[0];
                    int col = j + move[1];
                    if(isLegal(row, col, len)) dp1[i][j] += dp0[row][col];
                }
            }
        }
        dp0 = dp1;
    }
    return dp0[r][c] / Math.pow(8, K);
}

public boolean isLegal(int row, int col, int len){
    return row >= 0 && row < len && col >= 0 && col < len;
}

}