问题：
在给定的标准拨号盘上,跳跃N次可以产生的唯一数字的数量是多少,当你跳跃时,你必须像骑士棋子一样移动.您也无法登陆X之类的任何无效值,但您可以通过它们.
拨号器：
1 2 3
4 5 6
7 8 9
X 0 X
与此非常相似
Generate 10-digit number using a phone keypad
到目前为止我有什么但是疯狂的慢(Python 2.7)
jumpMap = {
1: [6,8],2: [7,9],3: [4,4: [0,3,5: [],6: [0,1,7],7: [2,6],8: [1,3],9: [2,4],0: [4,6]
}
def findUnique(start,jumps):
if jumps == 1:
# Base case 1 jump
return len(jumpMap[start])
if start == 5:
return 0
sum = 0
for value in (jumpMap[start]):
sum = sum + findUnique(value,jumps-1)
return sum
我猜测最简单的优化方法是进行某种记忆,但我无法弄清楚如何使用问题约束.
最佳答案
设K(k,n)是从密钥k开始的长度为n的唯一数的个数.然后,K(k,n 1)= sum(K(i,n)),其中i在可以从键k跳转到的键的范围内.
这可以使用动态编程有效地计算;这是一种占用O(n)时间和O(1)空间的方法：
jumpMap = [map(int,x) for x in '46,68,79,48,039,017,26,13,24'.split(',')]
def jumps(n):
K = [1] * 10
for _ in xrange(n):
K = [sum(K[j] for j in jumpMap[i]) for i in xrange(10)]
return sum(K)
for i in xrange(10):
print i,jumps(i)
更快：可以在log(n)时间和O(1)空间中计算答案.设M是10乘10矩阵,如果可以从i跳到j,则M [i,j] = 1,否则为0.然后求和(M ^ n * ones(10,1))就是答案.可以通过在log(n)时间中求平方来使用取幂来计算矩阵功率.这是使用numpy的一些代码：
jumpMap = [map(int,')]
M = numpy.matrix([[1 if j in jumpMap[i] else 0 for j in xrange(10)] for i in xrange(10)])
def jumps_mat(n):
return sum(M ** n * numpy.ones((10,1)))[0,0]
for i in xrange(10):
print i,jumps_mat(i)