给定一个电话键盘，如下所示：
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位数字。
当然可以在多项式时间内完成。在动态编程或记忆化中，这是极好的练习。
在本示例中，假设N（位数）等于10。
这样递归地考虑： 我可以使用从10开始的10位数字构造多少个数字1？
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）。
X
当涉及到复杂性时，主要的观察结果是您可以重用先前计算的解决方案。也就是说，例如回答 “从…开始3_有 _多少个6位数字8”_和 “4 _从…开始有多少个6位数字” 时，都可以使用 “ 从…开始 有 多少个5位数字” 的答案。 从 “ 。这种重用使复杂度从指数级变为多项式级。
3
8
4
让我们仔细看一下动态编程解决方案的复杂性：
这样的实现将通过以下方式填写矩阵：
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，因此以 线性时间 运行。
从头顶上写下来，如果有错别字请纠正我。
