935. Knight Dialer

Problem

Knight Dialer

Approach

• DFS & memorization Obviously, we can get answer by trying every number of the phone pad. In order to avoid TLE, it’s necessary to use memorization to reduce some duplicate calculation.

• DP Let DP[number][step] be the answer when start from number and the number of steps, step, is finished. So, DP[number][step] = DP[neighbor_1][step - 1] + … DP[neighbor_N][step - 1].

Code

1. approach 1

class Solution {
    private int[] dx = new int[]{-2, -1, 1, 2, -2, -1, 1, 2};
    private int[] dy = new int[]{-1, -2, -2, -1, 1, 2, 2, 1};
    private final static int MOD = (int)Math.pow(10, 9) + 7;
    private int tryDial(int N, int x, int y, int[][][] dp){
        if(N == 0){
            return 1;
        }
        if(N < 0){
            return 0;
        }
        if(dp[x][y][N] != 0){
            return dp[x][y][N];
        }
        int cnt = 0;
        for(int i = 0; i < dx.length; i ++){
            int nx = x + dx[i], ny = y + dy[i];
            if(nx < 0 || nx >= 4 || ny < 0 || ny >= 3){
                continue;
            }
            if((nx == 3 && ny == 0) || (nx == 3 && ny == 2)){
                continue;
            }
            cnt += tryDial(N - 1, nx, ny, dp);
            cnt %= MOD;
        }
        dp[x][y][N] = cnt;
        return cnt;
    }
    public int knightDialer(int N) {
        int ans = 0;
        int[][][] dp = new int[4][3][N];
        for(int i = 0; i <= 3; i ++){
            for(int j = 0; j <= 2; j ++){
                if(i == 3 && (j == 0 || j == 2)){
                    continue;
                }
                ans += tryDial(N - 1, i, j, dp);
                ans %= MOD;
            }
        }
        return ans;
    }
}

1. approach 2

class Solution {
    int mod = (int)Math.pow(10, 9) + 7;  
    int[][] neighbours = new int[][] {{4, 6}, {8,6}, {7,9}, {8,4}, {0,9,3}, {}, {1,7,0}, {2,6}, {1,3}, {2,4}};
    public int knightDialer(int N) {
        if(N == 0) return 0;
        int[][] dp = new int[10][N];
        for(int i = 0; i < 10; i ++){
            dp[i][0] = 1;
        }
        for(int step = 1; step < N; step ++){
            for(int id = 0; id < 10; id ++){
                for(int neighbor: neighbours[id]){
                    dp[id][step] += dp[neighbor][step - 1];
                    dp[id][step] %= mod;
                }
            }
        }
        int ans = 0;
        for(int i = 0; i < 10; i ++){
            ans += dp[i][N - 1];
            ans %= mod;
        }
        return ans;
    }
}