动态规划攻略之：下载插件

发表于

「这是我参与11月更文挑战的第21天，活动详情查看：2021最后一次更文挑战」

题目

小扣打算给自己的 VS code 安装使用插件，初始状态下带宽每分钟可以完成 1 个插件的下载。假定每分钟选择以下两种策略之一:

  • 使用当前带宽下载插件
  • 将带宽加倍（下载插件数量随之加倍）

请返回小扣完成下载 n 个插件最少需要多少分钟。

注意：实际的下载的插件数量可以超过 n 个

示例1：

1
2
3
4
5
6
7
8
9
ini复制代码输入：n = 2

输出：2

解释：
以下两个方案，都能实现 2 分钟内下载 2 个插件

方案一：第一分钟带宽加倍，带宽可每分钟下载 2 个插件；第二分钟下载 2 个插件
方案二：第一分钟下载 1 个插件，第二分钟下载 1 个插件

示例2：

1
2
3
4
5
6
7
8
9
ini复制代码输入：n = 4

输出：3

解释：
最少需要 3 分钟可完成 4 个插件的下载，以下是其中一种方案:
第一分钟带宽加倍，带宽可每分钟下载 2 个插件;
第二分钟下载 2 个插件;
第三分钟下载 2 个插件。。

解题思路

根据题意，我们可以利用动态规划的方法来解答此题。

我们定义 dp[i] 为下载 i 个插件所需的最优时间。

依照当前速度下载所需的时间为 dp[i] = dp[i - 1] + 1。

速度加倍所需的时间为 dp[i] = d[(i + 1) / 2] + 1。

那为什么 dp[i] = dp[(i + 1) / 2] 呢！

因为当我们速度加倍了，下载 i / 2 个插件时速度加倍，下一次便恰好下载到 i 个插件。也就是 i / 2 时才是最优解。

代码实现

1
2
3
4
5
6
7
8
9
10
java复制代码class Solution {
    public int leastMinutes(int n) {
        int[] dp = new int[n+1];
        dp[1] = 1;
        for (int i = 2; i <= n; i++){
            dp[i] = Math.min(dp[i-1]+1, dp[(i+1)/2]+1);
        }
        return dp[n];
    }
}

最后

  • 时间复杂度：O(n)
  • 空间复杂度：O(n)

**往期文章：

请你喝杯 ☕️ 点赞 + 关注哦～

  1. 阅读完记得给我点个赞哦，有👍 有动力
  2. 关注公众号— HelloWorld杰少，第一时间推送新姿势

最后，创作不易，如果对大家有所帮助，希望大家点赞支持，有什么问题也可以在评论区里讨论😄～**

本文转载自: 掘金

开发者博客 – 和开发相关的 这里全都有

0%