leetcode 935. Knight Dialer

class Solution {
    public int knightDialer(int N) {
        int cons = 1000000007;
        int[][] d = new int[10][N];
        int[][] m = new int[][]{{4, 6, -1}, {6, 8,-1}, {7, 9,-1}, {4, 8,-1}, 
                                {0,3,9}, {-1,-1,-1}, {1,7,0},{2,6,-1}, {1,3,-1},
                                {2,4,-1}};
        for (int i = 0; i < 10; ++i) d[i][0] = 1;
        for (int i = 1; i < N; ++i) {
            for (int j = 0; j < 10; ++j) {
                for (int k = 0; k < 3 && m[j][k] != -1; ++k) {
                    d[j][i] = (d[m[j][k]][i - 1] % cons + d[j][i]) % cons;
                }
            }
        }
        int ret = 0;
        for (int i = 0; i < 10; ++i) {
            ret = (ret + (d[i][N - 1] % cons)) % cons;
        }
        return ret;
    }
}

leetcode 935. Knight Dialer

原文：https://www.cnblogs.com/exhausttolive/p/10596967.html