package leetcode;

/**
 * https://leetcode.com/problems/knight-probability-in-chessboard/
 */
public class Problem688 {
    public double knightProbability(int N, int K, int r, int c) {
        // TODO
        // (-2, -1), (-1, -2), (1, -2), (2, -1), (2, 1), (1, 2), (-1, 2), (-2, 1)
        return 0;
    }

    public static void main(String[] args) {
        Problem688 prob = new Problem688();
        System.out.println(prob.knightProbability(3, 2, 0, 0)); // 0.0625
        System.out.println(prob.knightProbability(3, 3, 0, 0)); // 0.01563
    }
}

@@ -191,15 +191,485 @@
     
-// TODO
+Double%5B%5D%5B%5D%5B%5D memo = new Double%5BK + 1%5D%5BN%5D%5BN%5D;%0A        return knightProbability(N, K, r, c, memo);%0A    %7D%0A%0A    private static double knightProbability(int n, int k, int row, int col,%0A                                            Double%5B%5D%5B%5D%5B%5D memo) %7B%0A        if (row %3C 0 %7C%7C row %3E= n %7C%7C col %3C 0 %7C%7C col %3E= n) %7B%0A            return 0;%0A        %7D%0A        if (k == 0) %7B%0A            return 1;%0A        %7D%0A        if (memo%5Bk%5D%5Brow%5D%5Bcol%5D != null) %7B%0A            return memo%5Bk%5D%5Brow%5D%5Bcol%5D;%0A        %7D
 %0A   
@@ -759,146 +759,379 @@
     
-return 0
+double a = knightProbability(n, k - 1, row - 2, col - 1, memo)
 ;%0A    
-%7D%0A%0A
     
-public static void main(String%5B%5D args) %7B%0A        Problem688 prob = new Problem688();%0A        System.out.println(prob.
+double b = knightProbability(n, k - 1, row - 1, col - 2, memo);%0A        double c = knightProbability(n, k - 1, row + 1, col - 2, memo);%0A        double d = knightProbability(n, k - 1, row + 2, col - 1, memo);%0A        double e = knightProbability(n, k - 1, row + 2, col + 1, memo);%0A        double f = 
 knig
@@ -1148,106 +1148,347 @@
 ity(
-3, 2, 0, 0)); // 0.0625%0A        System.out.println(prob.knightProbability(3, 3, 0, 0)); // 0.01563
+n, k - 1, row + 1, col + 2, memo);%0A        double g = knightProbability(n, k - 1, row - 1, col + 2, memo);%0A        double h = knightProbability(n, k - 1, row - 2, col + 1, memo);%0A        double sum = a + b + c + d + e + f + g + h;%0A        double probability = sum / 8.0;%0A        memo%5Bk%5D%5Brow%5D%5Bcol%5D = probability;%0A        return probability;
 %0A   

Solve problem 688