骑士走键盘

algorithm

---

骑士在键盘上走日形状的个数

• 骑士在键盘上走日形状的个数，题目大意，在九宫格键盘的数字键上放置一个骑士，骑士走$N-1$步，走的方式按照日字形，没走一步，认为是形成一个数组，最后构成$N$位数，问能够形成多少个不同的数字。
• 例如：$N=1$，那么可以形成$0 \cdots 9$ 这么十个数字。再如:$N=2$那么可以形成如下数字$16,18 \cdots 04,06$
• 可以看到有如下的走法关系:

$$next= { {0:{4, 6}} {1:{6, 8 }} {2:{7, 9 }} {3:{4, 8 }} {4:{0, 3, 9 }} {5:{ } } {6:{0, 1, 7 }} {7:{2, 6}} {8:{1, 3}} {9:{2, 4}} \}$$

• 注意4和6能够走到0。

---

方法一：递归

• 直观想法，第一步有10种选择，后面的每一步的选择都可以有上述表格获取。所以我们遍历这10种第一步。剩下的步骤可以从上述表中获取下一个步骤的具体走法。假设我们用$f[k,i,n]$，来表示从数字$k$开始，走了$i$步之后，再走$n-i$步的方法。
• $next(i)$表示当前i能够跳到的数字集合，例如：$next(1)= {6,8}$。

$$f(k,i,n) = \sum_{j=0,a=next[k]}^{len(a)}{f(a_j,i+1,n)}$$

• 有个问题是，什么时候能够算作是完成一种走法呢？
• 完成一次走法必须满足的条件是走了n步，即$i=n$时。
• 所以有如下的基本情况：
• $i== n$，认为方法数为1，

    unordered_map<int, vector<int>> umap;
    const int M = int(1e9 + 7);
    int knightDialer(int N)
    {
        umap[0] = { 4, 6 };
        umap[1] = { 6, 8 };
        umap[2] = { 7, 9 };
        umap[3] = { 4, 8 };
        umap[4] = { 0, 3, 9 };
        umap[5] = {};
        umap[6] = { 0, 1, 7 };
        umap[7] = { 2, 6 };
        umap[8] = { 1, 3 };
        umap[9] = { 2, 4 };
        int c = 0;
        for (int i = 0; i < 10; i++) {
            c += knight(i, 1, N);
            c %= M;
        }
        return c;
    }
    int knight(int k, int step, int n)
    {
        if (step == n)
            return 1;
        auto list = umap[k];
        int size = list.size();
        int s = 0;
        for (int i = 0; i < size; i++) {
            int x = knight(list[i], step + 1, n);
            s += x % M;
            s %= M;
        }
        return s % M;
    }

• 时间复杂度:$T(n) =O(2^n)$。
• 空间复杂度:$S(n) = O(n)$。

---

方法二：转化为备忘录递归（自顶向下的方法）

• 上述方式存在子问题重复计算的情况，例如计算$f(0,1,n)$,需要计算 $f(4,2,n),f(6,2,n)$,计算$f(3,1,n)$时，也需要计算，$f(4,2,n)$，可以发现非常多的子问题需要重新计算，我们用map，也可以用数组，来缓存已经计算完的数据。对于已经获取的数据直接返回结果。
• 对于已经计算出来的符号排列结果用map来保存，例如map[i-j]=x，表示$f(i,j,n)$选择结果。

unordered_map<int, vector<int>> umap;
    unordered_map<string, int> cache;
    const int M = int(1e9 + 7);
    int knightDialer(int N)
    {
        umap.clear();
        cache.clear();
        umap[0] = { 4, 6 };
        umap[1] = { 6, 8 };
        umap[2] = { 7, 9 };
        umap[3] = { 4, 8 };
        umap[4] = { 0, 3, 9 };
        umap[5] = {};
        umap[6] = { 0, 1, 7 };
        umap[7] = { 2, 6 };
        umap[8] = { 1, 3 };
        umap[9] = { 2, 4 };
        int c = 0;
        for (int i = 0; i < 10; i++) {
            c += knight(i, 1, N);
            c %= M;
        }
        return c;
    }
    int knight(int k, int step, int n)
    {
        if (step == n)
            return 1;
        string key = to_string(k) + "-" + to_string(step);
        if (cache.find(key) != cache.end()) {
            return cache[key];
        }
        auto list = umap[k];
        int size = list.size();
        int s = 0;
        for (int i = 0; i < size; i++) {
            int x = knight(list[i], step + 1, n);
            s += x % M;
            s %= M;
        }
        cache[key] = s % M;
        return cache[key];
    }

• 时间复杂度：$T(n,f) = O(n^2)$。
• 空间复杂度：$O(10*n)$，需要使用哈希表。
• 超时不通过，可优化。

---

方法三：转化为备忘录递归（自底向上的方法）（转化为迭代计算）

• 假设$f[i,n]$ 表示以$i$开始，走$n$步的形成数字方法。
• 那么$f[i,n]$,可以由，$next(i)$可以跳$n-1$的数字的步数。

$$f[i,n] = \sum_{k=0,a=next(i)}^{len(a)}f[a[k],n-1]$$

• 基础情况：$f[i,0] = 1,i ] i \in [0,9]$

unordered_map<int, vector<int>> umap;
    const int M = int(1e9 + 7);
    int knightDialer(int N){
        umap[0] = { 4, 6 };
        umap[1] = { 6, 8 };
        umap[2] = { 7, 9 };
        umap[3] = { 4, 8 };
        umap[4] = { 0, 3, 9 };
        umap[5] = {};
        umap[6] = { 0, 1, 7 };
        umap[7] = { 2, 6 };
        umap[8] = { 1, 3 };
        umap[9] = { 2, 4 };
        int c = 0;
        int size = 10;
        vector<vector<int>> dp(size, vector<int>(N, 0));
        // base case #1
        for (int i = 0; i < size; i++) {
            dp[i][0] = 1;
        }
        for (int s = 1; s < N; s++) {
            for (int i = 0; i < size; i++) {
                auto next = umap[i];
                for (auto e : next) { //
                    dp[i][s] += dp[e][s - 1];
                    dp[i][s] %= M;
                }
            }
        }
        for (int i = 0; i < size; i++) {
            c += dp[i][N - 1];
            c %= M;
        }
        return c % M;
    }

• 时间复杂度:$O(2*10*N)$,空间复杂度：$O(10*N)$