给出如下所示的电话键盘:
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位数.