python - 如何找到从 1 到达 A 的最小合法跳跃次数？

Question

我在制定算法来解决这个问题时遇到了麻烦。怎么做到呢？

给定一个整数 A 表示目标位置。 Jack 最初站在位置 1。在任何时候，如果 Jack 在位置 X，那么他可以一步:

移动到 2 *X 位置。

移动到 3 *X 位置。

移动到 4 *X 位置。

移动到 5 *X 位置。

帮助 jack (和我😭)找到到达目的地位置的最少步数。

如果使用任意数量的移动都无法到达目标位置，则返回 -1。

我的尝试

def solve(A):
    currentpos=1
    jump=5
    Jno=0
    while currentpos<A:
        currentpos=currentpos*jump
        Jno+=1
        if currentpos==A:
            break
        elif currentpos>A:
            if jump==2:
                break
            else:
                jump-=1
        else:
            continue
    return Jno

Answer 1

已经发布了很多好的答案。无论如何，您可以尝试动态编程方法。该范例侧重于保存较小子问题的答案以供以后使用。我附上了一个示例代码:

A = 100
infinity = 2**32
dp = [infinity]*(A+1)
dp[1] = 0
for i in range(2, A+1):
    if i%5 == 0:
        dp[i] = min(dp[int(i/5)]+1, dp[i])
    if i%4 == 0:
        dp[i] = min(dp[int(i/4)]+1, dp[i])
    if i%3 == 0:
        dp[i] = min(dp[int(i/3)]+1, dp[i])
    if i%2 == 0:
        dp[i] = min(dp[int(i/2)]+1, dp[i])

print(dp[A])

解释 :A是目的地——对于这个例子，我刚刚将它设置为 100。

我创建了一个名为 infinity 的 int =2^32 我将用它填充数组dp .我认为这个问题不会让您找到大于 infinity 的目的地。 .
dp[i]将存储到达 i 所需的步数.因此，dp[1]设置为 0，因为它是我们的初始位置。

我将大小设为 dp成为 A+1这样dp将包含从 0...A 的索引。 (从 0 开始计数)

现在我们迭代 i从 2 到 A .在每一步，我们检查是否 i可被 2、3、4 或 5 整除。如果是，我们查看 dp的 i除以其中一个数字:

    if i%5 == 0:
        dp[i] = min(dp[int(i/5)]+1, dp[i])
    if i%4 == 0:
        dp[i] = min(dp[int(i/4)]+1, dp[i])
    if i%3 == 0:
        dp[i] = min(dp[int(i/3)]+1, dp[i])
    if i%2 == 0:
        dp[i] = min(dp[int(i/2)]+1, dp[i])

在每一步，为了找到达到i的最小步数，我们检查是否保留了 dp[i] 的原始值或将其替换为以前的值 dp+1因为需要一步才能到达i从以前的值。

示例:dp[1] = 0 .假设我们现在在 i=5 . i能被 5 整除。i/5=1 .目前，dp[5]=infinity .但是如果我们从 1 到 5 一步(这是合法的)，我们将总共采取 dp[1]+1=1步。 1 小于 infinity .因此我们替换dp[5]与 1。

这一直持续到我们迭代到 i=A .现在，dp[A]将保持到达 A 的最小步数.如果我们无法访问 A , dp[A]将等于 infinity .

该算法的运行时间是线性的，O(N)。

抱歉解释冗长，如果有人愿意，我可以编辑。