動態規劃攻略之:下載外掛

語言: CN / TW / HK

「這是我參與11月更文挑戰的第21天,活動詳情檢視:2021最後一次更文挑戰

題目

小扣打算給自己的 VS code 安裝使用外掛,初始狀態下頻寬每分鐘可以完成 1 個外掛的下載。假定每分鐘選擇以下兩種策略之一:

  • 使用當前頻寬下載外掛

  • 將頻寬加倍(下載外掛數量隨之加倍)

請返回小扣完成下載 n 個外掛最少需要多少分鐘。

注意:實際的下載的外掛數量可以超過 n 個

示例1: ``` 輸入:n = 2

輸出:2

解釋: 以下兩個方案,都能實現 2 分鐘內下載 2 個外掛

方案一:第一分鐘頻寬加倍,頻寬可每分鐘下載 2 個外掛;第二分鐘下載 2 個外掛 方案二:第一分鐘下載 1 個外掛,第二分鐘下載 1 個外掛 ```

示例2: ``` 輸入: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 時才是最優解。

程式碼實現

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傑少,第一時間推送新姿勢

最後,創作不易,如果對大家有所幫助,希望大家點贊支援,有什麼問題也可以在評論區裡討論😄~**