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

Question

我在制定解决此问题的算法时遇到了问题。怎么做到的？

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

1. 移动到 2 *X 位置。
2. 移动到 3 *X 位置。
3. 移动到 4 *X 位置。
4. 移动到 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=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 整除。如果可以，我们查看 i 的 dp除以其中一个数字:

    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)。

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