问题：
在给定的标准拨号盘上,跳跃N次可以产生的唯一数字的数量是多少,当你跳跃时,你必须像骑士棋子一样移动.您也无法登陆X之类的任何无效值,但您可以通过它们.
拨号器：
1 2 3 4 5 6 7 8 9 X 0 X@H_301_12@与此非常相似
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@H_301_12@我猜测最简单的优化方法是进行某种记忆,但我无法弄清楚如何使用问题约束.
最佳答案
设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)@H_301_12@更快：可以在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)@H_301_12@