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

Question

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

1 2 3
4 5 6
7 8 9
  0

从1开始可以形成多少个不同的10位数字？约束是从1位数到下一位数的运动类似于国际象棋游戏中骑士的运动.

例如.如果我们在1那么下一个数字可以是6或8如果我们在6那么下一个数字可以是1,7或0.

允许重复数字 - 1616161616是有效数字.

有多项式时间算法可以解决这个问题吗？问题要求我们只计算10位数字,而不一定列出数字.

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

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

Answer 1

当然可以在多项式时间内完成.这是动态编程或memoization的一个很好的练习.

让我们假设N(数字位数)等于10.

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

答案是

[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]

等等.当你的问题达成基本情况"多1位的数字是如何从那里开始X"(答案是很明显1).

在复杂性方面,关键的观察是您重用以前计算的解决方案.也就是说,在回答"从3那里开始有多少个6位数字8"和" 4有多少个6位数字开头"时,可以使用" 从多少个5位数开始"的答案.来自".这种重用使得复杂性从指数变为多项式.

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

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

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,因此在线性时间内运行.

从头顶写下来,如果有任何错别字,请纠正我.