骑士走键盘

标签（空格分隔）： algorithm

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

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

$next_=\left\{\begin{matrix} [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]]\\ \end{matrix}\right.$

注意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)$