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

难度: Medium

你正在玩一个整数游戏。从整数 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 <= 10⁹
0 <= maxDoubles <= 100

Submission

运行时间: 23 ms

内存: 16.0 MB

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

Explain

该题解采用了从目标值向起始值反推的策略。我们从 target 开始，尽可能地进行除以2的操作（对应原问题中的加倍操作），直到不能再除或者用完了所有的加倍次数 maxDoubles。每当遇到奇数时，我们先通过减1将其变为偶数，这样就可以继续进行除以2的操作。最后，如果没有加倍次数，直接一步步递减到1。这种方法是基于贪心算法的思想，即尽可能地利用加倍操作来最快减少距离，因为加倍操作的跳跃性远大于递增操作。

时间复杂度: O(log(target))

空间复杂度: O(1)

class Solution:
    def minMoves(self, target: int, maxDoubles: int) -> int:
        ans = 0  # 初始化步数计数
        while target != 1:  # 直到当前值降到1
            if target % 2:  # 如果是奇数
                target -= 1  # 先递减到偶数
                ans += 1  # 递增操作次数
            else:  # 如果是偶数
                if maxDoubles:  # 还有加倍次数
                    target //= 2  # 进行加倍操作的逆操作，即除以2
                    maxDoubles -= 1  # 使用掉一次加倍机会
                    ans += 1  # 递增操作次数
                else:  # 没有加倍次数，只能一步步递减
                    break
        return ans + target - 1  # 返回总的最小操作次数，包括剩余的递减操作次数

Explore

从 target 开始反向计算而不是从 1 开始直接计算的原因在于操作的逆向简化。直接计算需要在每步决策中选择加1或者加倍，这可能涉及到复杂的动态规划以预测未来的操作。而从 target 反向计算时，每一步的选择更为清晰（尤其是在 target 较大时），因为逆向操作（除以2或减1）通常直观且易于计算，简化了决策过程。此外，反向操作确保了每次操作都是必要的，避免了冗余的加倍操作。

在这个题解中，将奇数减1变成偶数以便进行除以2操作通常是最优的，因为这样可以最大限度地利用减半操作减少 target 的值。直接递增 target 的情况通常不会更优，因为这样做并不能有效地利用减半操作减少后续的操作次数。在没有加倍次数的限制下，减1后除以2显然是减少步数的更快方法。

在没有剩余加倍次数的情况下，直接逐步递减至1是唯一的操作方法，因为任何其他的操作（如尝试做其他复杂计算）都不会改变需要递减的总次数。由于加倍次数已经用完，无法通过任何其他策略进一步减少操作次数，因此这种策略是效率最高的。

贪心算法的策略尽可能使用加倍操作通常是非常有效的，因为加倍操作能极大地减少操作步数。然而，这种策略并不一定在所有情况下都是最优解。在特定条件下，如加倍次数非常有限或者目标值较小，可能存在更优的策略需要结合动态规划等方法来确定。但在大多数情况下，贪心策略提供了一种简单且效率较高的解决方案。