下载插件

1. 题目描述

给 VS code 安装使用插件，初始状态下带宽每分钟可以完成 1 个插件的下载。假定每分钟选择以下两种策略之一: 使用当前带宽下载插件 将带宽加倍（下载插件数量随之加倍） 请返回小扣完成下载 n 个插件最少需要多少分钟。 注意：实际的下载的插件数量可以超过 n 个 示例 1： 输入：n = 2 输出：2 解释： 以下两个方案，都能实现 2 分钟内下载 2 个插件 方案一：第一分钟带宽加倍，带宽可每分钟下载 2 个插件；第二分钟下载 2 个插件 方案二：第一分钟下载 1 个插件，第二分钟下载 1 个插件 示例 2： 输入：n = 4 输出：3 解释： 最少需要 3 分钟可完成 4 个插件的下载，以下是其中一种方案: 第一分钟带宽加倍，带宽可每分钟下载 2 个插件; 第二分钟下载 2 个插件; 第三分钟下载 2 个插件。 提示： 1 <= n <= 10^5

2. 分析

分析过程 状态定义：当前带宽表示每分钟可以下载的插件数量，初始值为 1。我们还需要一个变量来记录已经下载的插件数量和所用的分钟数。 回溯逻辑： 在每分钟，我们有两个选择： 使用当前带宽下载插件。 将带宽加倍，下一分钟下载插件时将会以新带宽下载。 如果当前已下载的插件数量达到或超过 n，则记录当前所用的分钟数。 递归调用这两种选择。 剪枝：为了避免不必要的计算，我们可以在每次调用时判断当前已下载插件数量与 n 的关系，并使用一个全局变量来记录最小的分钟数。

3. 代码

class Solution(object):
    def __init__(self):
        self.ans = float('inf')  # 初始化答案为无穷大

    def backTrack(self, n, cur, idx, cnt):
        if idx >= self.ans:  # 如果当前步数已经大于等于答案，剪枝
            return
        if cur >= n:  # 如果当前值已经达到或超过目标值
            self.ans = min(self.ans, idx)  # 更新答案
            return
        if cnt * 2 > 2**31 - 1:  # 如果当前倍数超过整数最大值，剪枝
            return
        # 不选择当前的cnt，将其加倍
        self.backTrack(n, cur, idx + 1, cnt * 2)
        # 选择当前的cnt
        self.backTrack(n, cur + cnt, idx + 1, cnt)

    def leastMinutes(self, n):
        self.backTrack(n, 0, 0, 1)  # 从0开始，步数为0，初始倍数为1
        return self.ans  # 返回最少的分钟数