935. Knight Dialer

Version #1 DP

71.11 %
class Solution {
    public int knightDialer(int N) {
        int[][] map = new int[][]{{4, 6}, {6, 8}, {7, 9}, {4, 8}, {3, 9, 0}, {}, {1, 7, 0}, {2, 6}, {1, 3}, {2, 4}};
        int[] prev = new int[10];
        int mod = (int)(1e9 + 7);
        Arrays.fill(prev, 1);
        for (int i = 2; i <= N; i++) {
            int[] curr = new int[10];
            for (int x = 0; x <= 9; x++) {
                for (int last : map[x]) {
                    curr[x] = (curr[x] + prev[last]) % mod;
                }
            }
            prev = curr;
        }
        int sum = 0;
        for (int i = 0; i <= 9; i++) {
            sum = (sum + prev[i]) % mod;
        }
        return sum;
    }
}