寻找从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

@Arjunkhera的答案思路很对--当你超调时返回一个“可怕”的结果，所以你从来不选择它--但需要避免在结果加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);
}