algorithm - 使用电话键盘生成 10 位数字

Question

给定如下所示的电话键盘:

1 2 3
4 5 6
7 8 9
  0

从1开始可以组成多少个不同的10位数字？约束是从一位数到下一位数的移动类似于国际象棋游戏中马的移动。

例如。如果我们在 1 那么下一个数字可以是 6 或 8如果我们在 6，那么下一位可以是 1、7 或 0。

允许重复数字 - 1616161616 是一个有效数字。

是否有解决此问题的多项式时间算法？该题要求我们只给出10位数字的个数，而不必列出数字。

编辑:我尝试将其建模为图形，每个数字都有 2 或 3 个数字作为其邻居。然后我使用 DFS 导航到 10 个节点的深度，然后每次达到 10 的深度时递增数字计数。这显然不是多项式时间。假设每个数字只有 2 个邻居，这将需要至少 2^10 次迭代。

这里的变量是位数。我已经采取了例如。的 10 位数字。它也可以是 n 位数字。

Answer 1

当然可以在多项式时间内完成。这是一个很好的练习 dynamic programming或 memoization .

假设 N(位数)等于 10。

像这样递归地思考它:我可以使用从 1 开始的 10 个数字构造多少个数字？

答案是

[number of 9-digit numbers starting from 8] +
[number of 9-digit numbers starting from 6].

那么有多少个“从 8 开始的 9 位数字”？那么，

[number of 8-digit numbers starting from 1] +
[number of 8-digit numbers starting from 3]

等等。当您遇到问题“从 X 开始有多少个 1 位数字”(答案显然是 1)时，就达到了基本情况。

当谈到复杂性时，关键的观察是您重复使用以前计算的解决方案。也就是说，例如，“有多少个 5 位数字从 3 开始” 的答案可以在回答“有多少个 6 位数字开始”时使用从 8 " 和 "从 4 开始有多少个 6 位数字 ".这种重用使复杂性从指数级崩溃为多项式级。

让我们仔细看看动态规划解决方案的复杂性:

这样的实现将按照以下方式填充矩阵:

num[1][i] = 1, for all 0<=i<=9   -- there are one 1-digit number starting from X.

for digits = 2...N
    for from = 0...9
        num[digits][from] = num[digits-1][successor 1 of from] +
                            num[digits-1][successor 2 of from] +
                            ...
                            num[digits-1][successor K of from]

return num[N][1]                 -- number of N-digit numbers starting from 1.

该算法一次只填充一个单元格，矩阵的维度为 10*N，因此在线性时间内运行。

---

从头到尾写下来，如有错别请指正