跳转至

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\)，那么我们可以得到 \(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
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)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
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);
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
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);
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
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)
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
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);
}

方法二

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
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;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
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;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
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
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
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;
}

评论