骑士走键盘

标签（空格分隔）： algorithm

---

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

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

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

---

方法一：递归

• 直观想法，第一步有10种选择，后面的每一步的选择都可以有上述表格获取。所以我们遍历这10种第一步。剩下的步骤可以从上述表中获取下一个步骤的具体走法。假设我们用，来表示从数字开始，走了步之后，再走步的方法。
• 表示当前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;
    }

• 时间复杂度:。
• 空间复杂度:。

---

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

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

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];
    }

• 时间复杂度：。
• 空间复杂度：，需要使用哈希表。
• 超时不通过，可优化。

---

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

• 假设 表示以开始，走步的形成数字方法。
• 那么,可以由，可以跳的数字的步数。

• 基础情况：

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;
    }

• 时间复杂度:
• 空间复杂度：