优化算法
优化算法
提问于 2016-04-09 07:28:18
问题：
在给定的标准拨号盘上，在跳跃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,8],
4: [0, 3, 9],
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我猜最简单的优化方法应该是使用某种记忆，但考虑到问题的限制，我不知道如何使用记忆。
回答 2
Stack Overflow用户
发布于 2016-04-09 08:45:13
设K( k，n)是长度为n的唯一数的个数，从键k开始。然后，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是具有Mi的10乘10矩阵，如果可以从i跳到j，j=1，否则为0。那么sum(M^n * ones(10，1))就是答案。矩阵的幂可以通过在log(n)时间内平方来使用幂运算来计算。下面是一些使用numpy的代码：
jumpMap = [map(int, x) for x in '46,68,79,48,039,,017,26,13,24'.split(',')]
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)Stack Overflow用户
发布于 2016-04-09 08:54:46
你可以使用lru_cache，它会记录调用：
from functools import lru_cache
jumpMap = {
1: [6,8],
2: [7,9],
3: [4,8],
4: [0, 3, 9],
5: [],
6: [0, 1, 7],
7: [2, 6],
8: [1, 3],
9: [2, 4],
0: [4, 6]
}
@lru_cache(maxsize=1000)
def findUnique(start, jumps):
if jumps == 1:
return len(jumpMap[start])
if start == 5:
return 0
sum = 0
for value in (jumpMap[start]):
sum = sum + findUnique(value, jumps-1)
return sum页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/36510897
复制相关文章
相似问题
腾讯云开发者
