优化算法

Question

问题：

在给定的标准拨号盘上，当你跳跃N次时，可以通过骑士棋子的走法移动。同时不能落到任何无效值上，如X。请问有多少个唯一的数字可以生成？你可以穿过无效值，但不能落在它们上面。

拨号器：

1 2 3

4 5 6

7 8 9

X 0 X

与此非常相似

使用电话键盘生成10位数字

我目前拥有的但速度极慢（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

我猜最简单的优化方式是使用某种记忆化方法，但是考虑到问题限制，我无法想出如何使用。

- anon

Answer 1

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的矩阵，其中M [i，j] = 1表示从i跳到j是可能的，否则为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)

- Paul Hankin

Answer 2

您可以使用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

- HYRY