减少到一：给定一个整数N，通过执行给定的操作将其减少到1

Question

给定一个整数 N，通过执行给定的操作将其减少到 1：- 在一个操作中，您可以从 N 中减去除 N 本身之外的 N 的任何除数。您的任务是找到将 N 减少到 1 的最小数字。

输出： 打印将 N 转换为 1 所需的最少运算次数。

输入1：5 输出1 3

输入：8 输出：3

def min_operations_to_one(N):
    dp = [0] * (N + 1)

    for i in range(2, N + 1):
        dp[i] = dp[i - 1] + 1  # Subtracting 1 from N

        for j in range(2, i):
            if i % j == 0:
                dp[i] = min(dp[i], dp[i // j] + 1)  # Subtracting divisor j from N

    return dp[N]

此代码给出 8 的错误输出

Answer 1

您的问题在于一行：带有

min

的行。您正在获取

i//j

的 dp 值，但这不是正确的操作。我们需要知道当前数字减去除数的 dp 值。

以 8 为例。我们知道 2 的值为 1，4 的值为 2。但是你不能只使用 2 作为前驱； 8-2 并没有让我们更接近我们的目标。我们需要知道的是减法的结果。我相信你需要比较

dp[i-j]

:

def min_operations_to_one(N):
    dp = [0] * (N + 1)

    for i in range(2, N + 1):
        dp[i] = dp[i-1]+1
        for j in range(2,i):
            if i % j == 0:
                dp[i] = min(dp[i], dp[i-j]+1 )
    print(dp)
    return dp[N]

print(min_operations_to_one(8))
print(min_operations_to_one(20))

输出：

[0, 0, 1, 2, 2, 3, 3, 4, 3]
3
[0, 0, 1, 2, 2, 3, 3, 4, 3, 4, 4, 5, 4, 5, 5, 5, 4, 5, 5, 6, 5]
5

Answer 2

我是这样理解的。数字N需要减至1。但是在每一步中，数字N只需要从它的除数中减去。（当然不是'N'本身不是必需的，因为如果你减去N，数字将是0 或负数）。找出所涉及的最少步骤。

如果这是你的任务， 如果输入是5， 五的约数 = 1 和 5 离开 5;5 - 1 = 4（步骤 -1）；4 - 1 = 3（步骤 -2）；3 - 1 = 2（步骤 -3）；2 - 1 = 1（步骤 -4） 所以，输出应该是 4。（你给出的是 3）

如果输入是8， 8 的约数 = 1, 2, 4, 8 留下8； 8 -4 = 4（步骤-1）；4 - 2 = 2（步骤-2）； 2 - 1 = 1（步骤-3）。 所以，输出应该是3 我只是严格按照算法进行计算：

def min_operations_to_one(N):
    count, i = 0, 0
    divisors = [x for x in range(N, 0, -1) if N%x == 0]
    while i < len(divisors):
        if N ==1 : break
        if N - divisors[i] >= 1:
            N = N - divisors[i]
            count = count +1
            i = i - 1
        i += 1
    return count

print(min_operations_to_one(5)) # output : 4
print(min_operations_to_one(8)) # output : 3