# C++ DP & DFS+memo sols

• DFS+memorization sol ------
space O(KN^2)
time O(K
N^2)

``````class Solution {
public:
//DFS with memorization
double knightProbability(int N, int K, int r, int c) {
dirs={{2,1},{2,-1},{1,2},{1,-2},{-2,1},{-2,-1},{-1,2},{-1,-2}};
result=vector<vector<vector<double>>>(K+1,vector<vector<double>>(N,vector<double>(N,-1.)));
return dfs(N,K,r,c);
}
private:
double dfs(int N, int K, int r, int c) {
if(r<0 || c<0 || r>=N || c>=N) return 0;
if(K==0) return 1;
if(result[K][r][c]!=-1) return result[K][r][c];
double prob=0;
for(const auto& dir:dirs) {
int rr=r+dir[0], cc=c+dir[1];
prob+=(1/8.*dfs(N,K-1,rr,cc));
}
return result[K][r][c]=prob;
}
vector<vector<int>> dirs;
vector<vector<vector<double>>> result;
};
``````

DP sol ------
space O(N^2)
time O(K*N^2)

``````class Solution {
public:
//DP
double knightProbability(int N, int K, int r, int c) {
if(r<0 || r>=N || c<0 || c>=N) return 0;

vector<vector<int>>dirs({{2,1},{2,-1},{1,2},{1,-2},{-2,1},{-2,-1},{-1,2},{-1,-2}});
vector<vector<double>> oldP(vector<vector<double>>(N,vector<double>(N,1.)));
vector<vector<double>> newP(vector<vector<double>>(N,vector<double>(N,0.)));
for(int l=1; l<=K; l++) {
for(int i=0; i<N; i++) {
for(int j=0; j<N; j++) {
newP[i][j]=0;
for(const auto& dir:dirs) {
int rr=i+dir[0], cc=j+dir[1];
if(rr<0 || rr>=N || cc<0 || cc>=N) continue;
newP[i][j]+=0.125*oldP[rr][cc];
}
}
}
oldP=newP;
}
return oldP[r][c];
}
};
``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.