摘要：題目鏈接這道題做，關(guān)鍵是注意對(duì)稱性，減少次數(shù)。同時(shí)注意第個(gè)條件這種情況發(fā)生在兩個(gè)值的和差值沒有的時(shí)候，也就是或者，也是同理。

題目鏈接：https://leetcode.com/problems...

這道題dfs做，關(guān)鍵是注意對(duì)稱性，減少dfs次數(shù)。同時(shí)注意第3個(gè)條件 No jumps through non selected key is allowed. 這種情況發(fā)生在兩個(gè)值的x和y差值沒有1的時(shí)候，也就是abs(nx-x) == 2或者abs(nx - x) == 0，y也是同理。

public class Solution {
    public int numberOfPatterns(int m, int n) {
        /* subproblem: dp[depth][i][j] = sum(dp[depth + 1][ni][nj]) if valid  
         */
        int count = 0;
        // start position: symmetry
        // 1, 3, 7, 9 and 2, 4, 6, 8
        boolean[][] visited = new boolean[3][3];
        count += dfs(m, n, 0, 0, 1, visited) * 4;
        count += dfs(m, n, 0, 1, 1, visited) * 4;
        count += dfs(m, n, 1, 1, 1, visited);
        return count;
    }

    private int dfs(int m, int n, int x, int y, int depth, boolean[][] visited) {
        int count = 0;
        if(depth == n) {
            count++;
            return count;
        }
        if(depth >= m) count++;
        visited[x][y] = true;
        // next step
        for(int i = 0; i < 3; i++) {
            for(int j = 0; j < 3; j++) {
                if(!visited[i][j]) {
                    // previous position was not visited
                    if(Math.abs(i - x) != 1 && Math.abs(j - y) != 1 && !visited[(i+x)/2][(j+y)/2]) continue;
                    count += dfs(m, n, i, j, depth + 1, visited);
                }
            }
        }
        visited[x][y] = false;
        return count;
    }
}