688. Knight Probability in Chess
2018-07-25 本文已影响0人
becauseyou_90cd
解题思路:
- 对于每一步(总步数:K)更新一次dp0[i][j]
- 当符合条件时: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;
}
}