C++ DP & DFS+memo sols


  • 1
    M

    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];
        }
    };
    

Log in to reply
 

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