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

你正在玩一个整数游戏。从整数 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 变为 1；

• 可以进行递减操作，将当前整数的值减 1；

• 可以进行折半操作，将当前整数的值除以 2，前提是当前整数为偶数。

上述游戏和题目描述中的游戏是等价的。但不同的是，题目描述中的游戏在每一次行动中，我们并不能知道是进行递增还是加倍操作。而在上述游戏中，如果当前整数为奇数，那么我们必须只能执行递减操作；如果当前整数为偶数，那么可以执行任意操作。

由于我们的目标是将整数变为 1，因此在当前整数为偶数时，我们应当贪心地执行折半操作。这也是可以证明的：

如果我们选择执行递减操作，那么有两种情况：

• 我们不断执行递减操作直到整数变为 1；
• 我们执行了 k 次递减操作，随后再执行折半操作。

对于第一种情况。我们可以先执行一次折半操作，这样后续的递减操作至少会减少一次；对于第二种情况，我们可以先执行一次折半操作，再执行 k/2 次递减操作，可以得到相同的结果，但操作次数减少了 k/2 次。

因此如果当前整数为偶数，并且还有剩余的折半操作次数，我们就执行折半操作，否则执行递减操作。

优化

在最坏的情况下，如果初始的折半操作次数为 0，那么我们会执行 target} - 1 次递减操作，时间复杂度为 O(\textit{target})，会超出时间限制。一种可行的优化方法是，任意时刻当折半操作次数为 0 时，剩余的操作只能为递减操作，我们直接返回之前使用的操作次数加上当前 target 的值减去 1 即可。

代码

[sol1-C++]

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

[sol1-Python3]

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 //= 2
        ans += (target - 1)
        return ans

复杂度分析

• 时间复杂度：O(\min(\log \textit{target}, \textit{maxDoubles}))。在上述代码的循环中，每两次循环就至少会有一次折半操作，而 target 最多可以被折半 O(\log \textit{target}) 次。并且折半操作有次数限制，不能超过 maxDoubles，因此时间复杂度为 O(\min(\log \textit{target}, \textit{maxDoubles}))。

• 空间复杂度：O(1)。