Question

2139. 得到目标值的最少行动次数

English Version

题目描述

你正在玩一个整数游戏。从整数 1 开始，期望得到整数 target 。

在一次行动中，你可以做下述两种操作之一：

• 递增，将当前整数的值加 1（即， x = x + 1）。
• 加倍，使当前整数的值翻倍（即，x = 2 * x）。

在整个游戏过程中，你可以使用 递增 操作 任意 次数。但是只能使用 加倍 操作 至多 maxDoubles 次。

给你两个整数 target 和 maxDoubles ，返回从 1 开始得到_ _target_ _需要的最少行动次数。

 

示例 1：

输入：target = 5, maxDoubles = 0
输出：4
解释：一直递增 1 直到得到 target 。

示例 2：

输入：target = 19, maxDoubles = 2
输出：7
解释：最初，x = 1 。
递增 3 次，x = 4 。
加倍 1 次，x = 8 。
递增 1 次，x = 9 。
加倍 1 次，x = 18 。
递增 1 次，x = 19 。

示例 3：

输入：target = 10, maxDoubles = 4
输出：4
解释：
最初，x = 1 。 
递增 1 次，x = 2 。 
加倍 1 次，x = 4 。 
递增 1 次，x = 5 。 
加倍 1 次，x = 10 。 

 

提示：

• 1 <= target <= 109
• 0 <= maxDoubles <= 100

解法

方法一：倒推 + 贪心

我们不妨从最终的状态开始倒推，假设最终的状态为 $target$，那么我们可以得到 $target$ 的前一个状态为 $target - 1$ 或者 $target / 2$，这取决于 $target$ 的奇偶性以及 $maxDoubles$ 的值。

如果 $target=1$，那么不需要任何操作，直接返回 $0$ 即可。

如果 $maxDoubles=0$，那么我们只能使用递增操作，因此我们需要 $target-1$ 次操作。

如果 $target$ 是偶数且 $maxDoubles>0$，那么我们可以使用加倍操作，因此我们需要 $1$ 次操作，然后递归求解 $target/2$ 和 $maxDoubles-1$。

如果 $target$ 是奇数，那么我们只能使用递增操作，因此我们需要 $1$ 次操作，然后递归求解 $target-1$ 和 $maxDoubles$。

时间复杂度 $O(\min(\log target, maxDoubles))$，空间复杂度 $O(\min(\log target, maxDoubles))$。

我们也可以将上述过程改为迭代的方式，这样可以避免递归的空间开销。

class Solution:
  def minMoves(self, target: int, maxDoubles: int) -> int:
    if target == 1:
      return 0
    if maxDoubles == 0:
      return target - 1
    if target % 2 == 0 and maxDoubles:
      return 1 + self.minMoves(target >> 1, maxDoubles - 1)
    return 1 + self.minMoves(target - 1, maxDoubles)

class Solution {
  public int minMoves(int target, int maxDoubles) {
    if (target == 1) {
      return 0;
    }
    if (maxDoubles == 0) {
      return target - 1;
    }
    if (target % 2 == 0 && maxDoubles > 0) {
      return 1 + minMoves(target >> 1, maxDoubles - 1);
    }
    return 1 + minMoves(target - 1, maxDoubles);
  }
}

class Solution {
public:
  int minMoves(int target, int maxDoubles) {
    if (target == 1) {
      return 0;
    }
    if (maxDoubles == 0) {
      return target - 1;
    }
    if (target % 2 == 0 && maxDoubles > 0) {
      return 1 + minMoves(target >> 1, maxDoubles - 1);
    }
    return 1 + minMoves(target - 1, maxDoubles);
  }
};

func minMoves(target int, maxDoubles int) int {
  if target == 1 {
    return 0
  }
  if maxDoubles == 0 {
    return target - 1
  }
  if target%2 == 0 && maxDoubles > 0 {
    return 1 + minMoves(target>>1, maxDoubles-1)
  }
  return 1 + minMoves(target-1, maxDoubles)
}

function minMoves(target: number, maxDoubles: number): number {
  if (target === 1) {
    return 0;
  }
  if (maxDoubles === 0) {
    return target - 1;
  }
  if (target % 2 === 0 && maxDoubles) {
    return 1 + minMoves(target >> 1, maxDoubles - 1);
  }
  return 1 + minMoves(target - 1, maxDoubles);
}

方法二

class Solution:
  def minMoves(self, target: int, maxDoubles: int) -> int:
    ans = 0
    while maxDoubles and target > 1:
      ans += 1
      if target % 2 == 1:
        target -= 1
      else:
        maxDoubles -= 1
        target >>= 1
    ans += target - 1
    return ans

class Solution {
  public int minMoves(int target, int maxDoubles) {
    int ans = 0;
    while (maxDoubles > 0 && target > 1) {
      ++ans;
      if (target % 2 == 1) {
        --target;
      } else {
        --maxDoubles;
        target >>= 1;
      }
    }
    ans += target - 1;
    return ans;
  }
}

class Solution {
public:
  int minMoves(int target, int maxDoubles) {
    int ans = 0;
    while (maxDoubles > 0 && target > 1) {
      ++ans;
      if (target % 2 == 1) {
        --target;
      } else {
        --maxDoubles;
        target >>= 1;
      }
    }
    ans += target - 1;
    return ans;
  }
};

func minMoves(target int, maxDoubles int) (ans int) {
  for maxDoubles > 0 && target > 1 {
    ans++
    if target&1 == 1 {
      target--
    } else {
      maxDoubles--
      target >>= 1
    }
  }
  ans += target - 1
  return
}

function minMoves(target: number, maxDoubles: number): number {
  let ans = 0;
  while (maxDoubles && target > 1) {
    ++ans;
    if (target & 1) {
      --target;
    } else {
      --maxDoubles;
      target >>= 1;
    }
  }
  ans += target - 1;
  return ans;
}