935. 骑士拨号器

发表于 分类于 阅读次数： Waline： 本文字数： 525 阅读时长 ≈ 2 分钟

考点

  • 状态机DP
  • 网格图DP

思路

1. 问题抽象

电话键盘上的数字 \(0\sim 9\) 可以看作一个包含 10 个节点的有向图。 若骑士（Knight）可以从数字 \(x\) 通过一次马步跳到数字 \(y\)，则在图中存在一条有向边 \(x \to y\)。

问题等价于：

在该有向图上，统计长度为 \(n\) 的 walk（允许重复节点）的总数。

2. 状态定义

定义动态规划状态： \[ f(i, d) = \text{长度为 } i \text{，且最后一个数字为 } d \text{ 的合法号码个数} \] 其中：

  • \(i \in [1, n]\)
  • \(d \in \{0,1,2,\dots,9\}\)

3. 初始值（Base Case）

当号码长度为 1 时，每个数字都可以单独构成一个合法号码，因此： \[ f(1, d) = 1 \quad \forall d \in \{0,1,\dots,9\} \]

4. 状态转移方程

设 \(\text{Next}(x)\) 表示骑士从数字 \(x\) 可以跳到的所有数字集合。

若在长度为 \(i\) 时停在数字 \(x\)，则下一步可以跳到任意 \(y \in \text{Next}(x)\)。因此有： \[ f(i+1, y) \;+=\; f(i, x) \quad \forall x \in \{0,\dots,9\},\; \forall y \in \text{Next}(x) \] 完整的转移关系可以写为： \[ f(i+1, y) = \sum_{\substack{x \\ x \to y}} f(i, x) \] 由于结果可能非常大，所有计算均在模数下进行： \[ f(i+1, y) = \left( f(i+1, y) + f(i, x) \right) \bmod (10^9 + 7) \]

5. 结果计算

当长度达到 \(n\) 时，任意数字结尾的号码都是合法的，因此最终答案为： \[ \text{Answer} = \sum_{d=0}^{9} f(n, d) \;\bmod\; (10^9 + 7) \]

6. 代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
class Solution {
public:
    static const int maxn = 5e3 + 5, mod = 1e9 + 7;
    int knightDialer(int n) {
        vector<vector<int>> mp(10);
        mp[0] = {4, 6};
        mp[1] = {6, 8};
        mp[2] = {7, 9};
        mp[3] = {4, 8};
        mp[4] = {0, 3, 9};
        mp[5] = {};
        mp[6] = {0, 1, 7};
        mp[7] = {2, 6};
        mp[8] = {1, 3};
        mp[9] = {4, 2};
        long long f[maxn][10];
        memset(f, 0, sizeof(f));
        for (int i = 0; i < 10; ++i)
            f[1][i] = 1;
        for (int i = 1; i < n; ++i) {
            for (int st = 0; st < 10; ++st) {
                for (int& ed : mp[st]) {
                    f[i + 1][ed] = (f[i + 1][ed] + f[i][st]) % mod;
                }
            }
        }
        long long res = 0;
        for (int i = 0; i < 10; ++i)
            res = (res + f[n][i]) % mod;
        return res;
    }
};