Accepted Recursive Solution, better then iterative solutions for big N.


  • 0
    A

    Solution Runtime is 8^k, perform better than iterative DP solution when N is big number

          public double knightProbability(int N, int K, int r, int c) {
              if(K==0)
                  return 1.0;
            double[][][] solutionCache =new double[N][N][K+1];
            for(int i=0;i< N; i++)
                for(int j=0;j<N; j++)
                    Arrays.fill(solutionCache[i][j],-1);
            return Solve (r,c, N, K, solutionCache);
        }
        private double Solve(int r, int c, int n, int k,double[][][] solutionCache){
            if(r<0||r>=n||c<0||c>=n||k<=0)
                return 0;
            int[][] directions ={{2,1},{2,-1},{-2,1},{-2,-1},{1,2},{1,-2},{-1,2},{-1,-2}};
            if(solutionCache[r][c][k]<0){
                double score =0;
                if(k==1){
                    for(int i=0;i<directions.length; i++)
                        score+=((r+directions[i][0]>=00&&r+directions[i][0]<n&& c+ directions[i][1]>=0&&c+ directions[i][1]<n)?1:0);
                }
                else{
                    for(int i=0;i<directions.length; i++)
                        score+=Solve(r+directions[i][0], c+ directions[i][1], n, k-1, solutionCache);
                }
                solutionCache[r][c][k] =score/8;
            }
            return solutionCache[r][c][k];
        }
    

Log in to reply
 

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