Knights Probability in Chessboard Dynamic Programming | Leetcode-688 (Medium) Solution

NADOS also enables doubt support, career opportunities and contests besides free of charge content for learning. In this problem, we discuss the knights probability in chessboard problem using dynamic programming in java. In this problem,

1. You are given a N*N chessboard and the starting position of the knight in the chessboard.
2. The rows and columns are 0 indexed, so the top-left square is (0, 0), and the bottom-right square is (N-1, N-1).
3. You have to find the probability of knight to remain in the chessboard after exactly k number of moves.

Note - The knight continues moving until it has made exactly K moves or has moved off the chessboard.

[dynamicuday]

Huge respect for u awesome....maza agya aap se padh ke .I feel blessed !!!!

[AYJ]

sir jo question koi or nhi samja sakta vo ap ese samja dete ho ki m bhul ni pata tysm 😀

[kunalkheeva]

This is it! finest explanation! and to the point!

[LeoLeo-nxgi]

Thanx Sir sorry maine pehle ke videos me aapko baar baar pareshan kiya ho DP bol bol kr aaj aapne itna sikhaya h thanx Sir really a big thanx

[jasmeenkaur]

Huge respect for this channel 😀😀😀 thanks alot sirr

[anuragagnihotri]

Bas Sumit bas, kitna acha samjhaoge bhai

[Radaradababurao]

if some one is facing problem with printing answer in cpp
just use
cout<<setprecision(17);
cout<<sum;

it will work

[ashwinnema]

Sir one text case is wrong here I have checked it on geeksforgeeks 8
3
2
4
Its expected output is wrong please verify it on your side

[yashwantkumar]

Sir apke purane set of questions outdated bata rha hai kya again aap link share karoge ??

[beinghappy]

Working C++ Code
double knightProbability(int n, int k, int row, int column) {
//knight probability in chessboard
int x[] = {1, 1, -1, -1, 2, 2, -2, -2};
int y[] = {2, -2, 2, -2, 1, -1, 1, -1};

//double curr[n][n];
//double next[n][n];
vector<vector<double>>curr(n, vector<double>(n, 0.0));
vector<vector<double>>next(n, vector<double>(n, 0.0));
curr[row][column] = 1;
for(int move = 1;move<=k;move++){
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
if(curr[i][j]!=0){
for(int k=0;k<8;k++){
int ni = i + x[k];
int nj = j + y[k];
if(ni>=0 and ni<n and nj>=0 and nj<n){
next[ni][nj]+= curr[i][j]/8.0;
}
}
}
}
}
curr = next;
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
next[i][j] = 0.0;
}
}
}
double sum = 0.0;
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
sum += curr[i][j];
}
}
return sum;
}

[mehulmulchandani]

Sir please make a video on how to make proper notes of your videos

[yogeshdixit]

due to hindi content many those who dont know hindi are missing huge in their coding carrier

[ayushgoel]

Sir dp on 2d arrays ke problems bhi jaroor cover kijiyega jaise - max sum rectangle in 2d array, max size square of all 1s etc..., waise sir abhi dp mein aur kitne patterns bacche hai ??

[rahulbhatia]

Sir pls make videos on tries encoding topic. Thanks

[aman]

Sr wo loop wala treeka to bta do knigth ke 8 move check krne ka

[harshtekriwal]

Sir wo 8 moves loop se likne ka tarika btadena kisi video mei.

[bhupeshkumar]

Sir apne kaha tha backtracking me permutaton comination ke 30 sawaal banaoge vaha toh 20 hi hai

[priyanshu.tiwari]

Sir, please set precision for the final answer, so that people in other languages can also submit the solution. It's not accepting 0.06250000 when the answer is 0.0625

[XEQUTE]

getting an errror that IndexError: list assignment index out of range
on line 39