“This is the 21st day of my participation in the Gwen Challenge in November. See details: The Last Gwen Challenge in 2021”

The title

Xiao Kou plans to use plug-ins for his OWN VS Code installation. In the initial state, the bandwidth can complete 1 plug-in download per minute. Assume one of the following two strategies is selected per minute:

  • Download the plug-in using the current bandwidth

  • Double the bandwidth (double the number of plug-ins downloaded)

Please return to the button to complete the n plug-in download the minimum number of minutes.

Note: The actual number of plug-ins downloaded can exceed N

Example 1:

Input: n = 2 Output: 2 Description: Two plug-ins can be downloaded in two minutes. Solution 1: Double the bandwidth in the first minute to download two plug-ins per minute. Download two plug-ins in the second minute Solution 2: Download one plug-in in the first minute and one plug-in in the second minuteCopy the code

Example 2:

Input: n = 4 Output: 3 Description: It takes at least 3 minutes to download four plug-ins. One solution is as follows: The bandwidth is doubled in the first minute, and two plug-ins can be downloaded per minute. Second minute download 2 plugins; Third minute download 2 plugins.Copy the code

Their thinking

We can use the method of dynamic programming to solve the problem.

We define DP [I] as the optimal time to download I plug-ins.

The download time at the current speed is dp[I] = dp[i-1] + 1.

The time required to double the speed is dp[I] = d[(I + 1) / 2] + 1.

So why is dp[I] = dp[I + 1] / 2?

Because when we double the speed, we double the speed when we download I / 2 plug-ins, and we download exactly I plug-ins the next time. I over 2 is the best solution.

Code implementation

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);
        }
        returndp[n]; }}Copy the code

The last

  • Time complexity: O(n)
  • Space complexity: O(n)

Previous articles:

  • Binary tree brush summary: binary search tree properties
  • Binary tree summary: binary tree properties
  • Binary tree summary: binary tree modification and construction
  • StoreKit2 smells this good? Yeah, I tried it. It smells good
  • After reading this article, I am no longer afraid of being asked how to construct a binary tree.
  • The game guys are trying to get people to pay again. That’s bad!
  • Take you rolled a netease holding cloud music home | adapter
  • Netease Cloud Music Home Page (3)
  • Netease Cloud Music Home Page (2)
  • Netease Cloud Music Home Page (a)
  • Does the code need comments? Write and you lose
  • I would not study in Codable for a long time. They are for fun
  • IOS handles web data gracefully. Do you really? Why don’t you read this one
  • UICollectionView custom layout! This one is enough

Please drink a cup ☕️ + attention oh ~

  1. After reading, remember to give me a thumbs-up oh, there is 👍 power
  2. Follow the public number – HelloWorld Jie Shao, the first time push new posture

Finally, creation is not easy, if it is helpful to you, I hope you can praise and support, what questions can also be discussed in the comments section 😄 ~ **