Knight Dialer

KnightDialer.java

class Solution {
    int mod = (int) Math.pow(10, 9) + 7;
    int[][] directions = new int[][] {
        {-2, 1}, 
        {-2, -1},
        {2, -1},
        {2, 1},
        {-1, 2},
        {-1, -2},
        {1, 2},
        {1, -2}
    };
    public int knightDialer(int n) {
        
        // 还有溢出问题，全部换成long
        long[][][] cache = new long[4][3][n + 1];
        int[][] mat = new int[][] {
            {1, 2, 3},
            {4, 5, 6},
            {7, 8, 9},
            {0, 0, 0}
        };
        int rows = 4;
        int cols = 3;
        long res = 0;
        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < cols; j++) {
                // res += helper(mat, n, i, j, 1, cache) % mod;
                // 上面那样子还是会溢出
                res = (res + helper(mat, n, i, j, 1, cache)) % mod;
            }
        }
        return (int) res;
    }
    private long helper(int[][] mat, int n, int i, int j, int index, long[][][] cache) {
        if (!isValid(mat, i, j)) {
            return 0;
        }
        if (index == n) {
            return 1;
        }
        if (cache[i][j][index] != 0) {
            return cache[i][j][index];
        }
        long curr = 0;
        for (int[] d : directions) {
            int mi = i + d[0];
            int mj = j + d[1];
            if (isValid(mat, mi, mj)) {
                // curr += helper(mat, n, mi, mj, index + 1, cache) % mod;
                curr = (curr + helper(mat, n, mi, mj, index + 1, cache)) % mod;
            }
        }
        cache[i][j][index] = curr;
        return curr;
        
    }
    private boolean isValid(int[][] mat, int i, int j) {
        if (i == 3 && j == 0 || i == 3 && j == 2) {
            return false;
        }
        int rows = mat.length;
        int cols = mat[0].length;
        return i >= 0 && j >= 0 && i < rows && j < cols;
    }
}