What is the main strategy for Minimum Moves to Reach Target Score?

The optimal strategy is reverse greedy: start at the target, decrement if odd, halve if even and doubles remain, counting moves until reaching 1.

Why does working backward simplify this problem?

It ensures that every double operation is applied at the most beneficial step, avoiding unnecessary increments and minimizing total moves.

How do odd numbers affect move calculation?

When the target is odd, you must decrement before halving to maintain integer values, ensuring the greedy invariant holds.

Can the solution handle very large target values efficiently?

Yes, because halving reduces the target logarithmically, the reverse greedy approach remains fast even for large targets up to 10^9.

What is the failure mode if maxDoubles is ignored?

Ignoring maxDoubles can result in attempting impossible double operations, causing overestimation of progress and incorrect minimal moves.

#2139

Medium

auto_awesome贪心·invariant

LeetCode 题解工作台

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

你正在玩一个整数游戏。从整数 1 开始，期望得到整数 target 。在一次行动中，你可以做下述两种操作之一：递增，将当前整数的值加 1（即， x = x + 1 ）。加倍，使当前整数的值翻倍（即， x = 2 * x ）。在整个游戏过程中，你可以使用递增操作任意次数。但是只能使…

数学贪心

题目描述

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

lightbulb

解题思路

方法一：倒推 + 贪心

我们不妨从最终的状态开始倒推，假设最终的状态为 $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))$ 。

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

1

2

3

4

5

6

7

8

9

10

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)

speed

复杂度分析

指标	值
时间	complexity is O(log target) because each halving reduces the number substantially, and space complexity is O(1) since only counters and variables are needed. Using the reverse approach avoids extra storage.
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
Check if the candidate recognizes that working backward simplifies the greedy decision.
question_mark
Listen for correct handling of odd target values before doubling.
question_mark
Verify the candidate counts moves while respecting maxDoubles constraint.

warning

常见陷阱

外企场景

error
Attempting to always double without checking remaining maxDoubles may overshoot minimal moves.
error
Incrementing forward from 1 without considering reverse halving strategy leads to unnecessary steps.
error
Failing to handle odd targets correctly before halving can increase move count.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Allow multiple doubling operations per move and adjust the greedy logic accordingly.
arrow_right_alt
Change the starting integer from 1 to any positive integer, requiring modified backward calculations.
arrow_right_alt
Limit total moves instead of doubles and ask whether reaching target is possible.

help

常见问题

外企场景

继续练习

#2160 拆分数位后四位数字的最小和 #2178 拆分成最多数目的正偶数之和 #2195 向数组中追加 K 个整数