找到从 x 到 y 的最少操作

Question

仍在与递归作斗争。我有一个代码应该让我从 x 到 y 的操作最少。仅乘以 2 或加 +1 例如从 7 到 12 ...它的 5 个操作，因为你需要五次 +1。我的代码对我来说不能正常工作，我无法弄清楚我缺少什么才能使其正确。

public static int minOps(int x,int y)
{
    if (x >= y) return 0;
        int add = 1 + minOps(x + 1, y);
        int mul = 1 + minOps(x * 2, y);
    return Math.min(add, mul);
}

Answer 1

您没有考虑到超调是不合法的，因此返回 0 是不正确的。只需在您的基本案例中更改以下内容

if(x > y) return Integer.MAX_VALUE;
if(x == y) return 0;

Answer 2

有正确的想法 - return 超出时的“可怕”结果，所以你永远不会 select - 但需要在添加时避免潜在的溢出1 到结果：

public static int minOps(int x,int y)
{
    // Return 1 less that MAX_VALUE, so adding 1 doesn't overflow.
    // You'll never get as far as here anyway, your stack will overflow long
    // before, so subtracting 1 makes no practical difference.
    if (x > y) return Integer.MAX_VALUE - 1;
    if (x >= y) return 0;

    int add = 1 + minOps(x + 1, y);
    int mul = 1 + minOps(x * 2, y);
    return Math.min(add, mul);
}

或者，您可以推迟加 1：

    if (x > y) return Integer.MAX_VALUE;
    if (x >= y) return 0;

    int add = minOps(x + 1, y);
    int mul = minOps(x * 2, y);
    return 1 + Math.min(add, mul);

因为 add 和 mul 中至少有一个不等于 MAX_VALUE。

找到从 x 到 y 的最少操作

finding the minimum operations to get from x to y

java

recursion

operation

minimum

backtracking