题目描述

注意越过点的情况，判断如果当前状态是否能越过中间点

压缩dp

$O(n\*9\*2^9\*9)(n次,9个数字,2^9个状态,每个状态9个转移)$

Java 代码

class Solution {
    public int numberOfPatterns(int m, int n) {
        // 0 1 2
        // 3 4 5
        // 6 7 8
        int[][] map=new int[9][9];
        int[][][] dp = new int[n + 1][9][1 << 9];
        for(int i=0;i<9;i++){
            dp[1][i][1<<i]=1;   // start case
            Arrays.fill(map[i],-1);
        }
        map[2][6]=map[6][2]=map[0][8]=map[8][0]=4; // pre requisite 
        map[0][2]=map[2][0]=1;
        map[3][5]=map[5][3]=4;
        map[6][8]=map[8][6]=7;
        map[0][6]=map[6][0]=3;
        map[1][7]=map[7][1]=4;
        map[2][8]=map[8][2]=5;
        for (int k = 2; k <= n; k++) {  // times
            for (int i = 0; i < 9; i++) {   // end with
                for (int j = 0; j < (1 << 9); j++) {    // state
                    if ((j & (1 << i)) == 0 || count(j) != k) continue;     // illegal state
                    int pst = j - (1 << i);     // prev state
                    for (int l = 0; l < 9; l++) {   // from pre number
                        if (map[i][l] == -1 || (j & (1 << map[i][l])) != 0){  // check if possible
                            dp[k][i][j] += dp[k - 1][l][pst];
                        }
                    }
                }
            }
        }
        int res=0;
        for(int i=m;i<=n;i++){
            for(int j=0;j<9;j++){
                for(int k=0;k<(1<<9);k++){
                    res+=dp[i][j][k];
                }
            }
        }
        return res;
    }

    int count(int n) { // count digit
        int res = 0;
        while (n != 0) {
            if ((n & 1) == 1) {
                res++;
            }
            n = n >> 1;
        }
        return res;
    }
}