package leetcode;

/**
 * https://leetcode.com/problems/knight-dialer/
 */
public class Problem935 {
    public int knightDialer(int N) {
        // TODO
        // 1 -> [6, 8]
        // 2 -> [7, 9]
        // 3 -> [4, 8]
        // 4 -> [0, 3, 9]
        // 5 -> []
        // 6 -> [0, 1, 7]
        // 7 -> [2, 6]
        // 8 -> [1, 3]
        // 9 -> [2, 4]
        // 0 -> [4, 6]
        return 0;
    }

    public static void main(String[] args) {
        Problem935 prob = new Problem935();
        System.out.println(prob.knightDialer(1)); // 10
        System.out.println(prob.knightDialer(2)); // 20
        System.out.println(prob.knightDialer(3)); // 46
        System.out.println(prob.knightDialer(5000)); // 406880451
    }
}

@@ -143,38 +143,110 @@
     
-// TODO%0A        // 1 -%3E %5B
+int%5B%5D%5B%5D moves = new int%5B10%5D%5B%5D;%0A        moves%5B0%5D = new int%5B%5D%7B4, 6%7D;%0A        moves%5B1%5D = new int%5B%5D%7B
 6, 8
-%5D
+%7D;
 %0A   
@@ -254,22 +254,35 @@
     
-// 2 -%3E %5B
+moves%5B2%5D = new int%5B%5D%7B
 7, 9
-%5D
+%7D;
 %0A   
@@ -290,22 +290,35 @@
     
-// 3 -%3E %5B
+moves%5B3%5D = new int%5B%5D%7B
 4, 8
-%5D
+%7D;
 %0A   
@@ -326,25 +326,38 @@
     
-// 4 -%3E %5B
+moves%5B4%5D = new int%5B%5D%7B
 0, 3, 9
-%5D
+%7D;
 %0A   
@@ -365,44 +365,70 @@
     
-// 5 -%3E %5B%5D%0A        // 6 -%3E %5B
+moves%5B5%5D = new int%5B%5D%7B%7D;%0A        moves%5B6%5D = new int%5B%5D%7B
 0, 1, 7
-%5D
+%7D;
 %0A   
@@ -436,22 +436,35 @@
     
-// 7 -%3E %5B
+moves%5B7%5D = new int%5B%5D%7B
 2, 6
-%5D
+%7D;
 %0A   
@@ -472,22 +472,35 @@
     
-// 8 -%3E %5B
+moves%5B8%5D = new int%5B%5D%7B
 1, 3
-%5D
+%7D;
 %0A   
@@ -508,62 +508,287 @@
     
-// 9 -%3E %5B2, 4%5D%0A        // 0 -%3E %5B4, 6%5D%0A  
+moves%5B9%5D = new int%5B%5D%7B2, 4%7D;%0A        Long%5B%5D%5B%5D memo = new Long%5BN + 1%5D%5B10%5D;%0A        long answer = 0;%0A        for (int i = 0; i %3C= 9; i++) %7B%0A            answer += knightDialer(moves, i, N - 1, memo) %25 (1_000_000_000 + 7);%0A        %7D%0A
       
+  
 return 
-0
+(int) (answer %25 (1_000_000_000 + 7))
 ;%0A  
@@ -801,21 +801,22 @@
    p
-ublic
+rivate
  static 
 void
@@ -815,312 +815,438 @@
 tic 
-void main(String%5B%5D args) %7B%0A        Problem935 prob = new Problem935();%0A        System.out.println(prob.knightDialer(1)); // 10%0A        System.out.println(prob.knightDialer(2)); // 20%0A        System.out.println(prob.knightDialer(3)); // 46%0A        System.out.println(prob.knightDialer(5000)); // 406880451
+long knightDialer(int%5B%5D%5B%5D moves, int position, int n, Long%5B%5D%5B%5D memo) %7B%0A        if (n == 0) %7B%0A            return 1;%0A        %7D%0A        if (memo%5Bn%5D%5Bposition%5D != null) %7B%0A            return memo%5Bn%5D%5Bposition%5D;%0A        %7D%0A        long count = 0;%0A        for (int move : moves%5Bposition%5D) %7B%0A            count += knightDialer(moves, move, n - 1, memo) %25 (1_000_000_000 + 7);%0A        %7D%0A        memo%5Bn%5D%5Bposition%5D = count;%0A        return count;
 %0A   

Solve problem 935