Hi 👋

  • Wechat: RyukieW
  • 📦 Technical article archive
  • 🐙 making
My personal project Mine Elic endless sky ladder Dream of books
type The game financial
AppStore Elic Umemi

A, the title

Give you a piece of string of length N, please cut the string into m segments of integer length (m and n are integers, n>1 and m>1), the length of each segment of string is denoted by k[0],k[1]… K (m – 1).

Excuse me [1] [0] k k… What is the largest possible product of *k[m-1]?

For example, if the length of a string is 8 and we cut it to lengths of 2, 3, and 3, the maximum product we get is 18.

Example 1:

Input: 2 Output: 1 Description: 2 = 1 + 1, 1 × 1 = 1Copy the code

Example 2:

Input: 10 Output: 36 Description: 10 = 3 + 3 + 4, 3 × 3 × 4 = 36Copy the code

Tip:

2 <= n <= 58

343: leetcode-cn.com/problems/in…

Source: LeetCode

Copyright belongs to collar network. Commercial reprint please contact the official authorization, non-commercial reprint please indicate the source.

Two, dynamic programming

Dynamic programming is a hot topic in interviews.

2.1 What scenarios are suitable for dynamic programming?

  • If the question is:
    • Finding the optimal solution to a problem (usuallyThe maximumorThe minimum value)
    • And the problem can be decomposed into a number of subproblems
    • And there are smaller subproblems that overlap between the word problems
  • You can consider using dynamic programming to solve this problem

2.2 Is this problem suitable for dynamic programming?

  • We define the maximum value of the product of a string of length n into segments as a functionf(n).
  • Let’s say we cut the first cut at a length of zeroI (0 < I < n)So I cut the rope to a length ofiandn-iThe two places.
  • We want to get the optimal solution to the whole problemf(n)So we’re going to use the same optimization method to make the length zeroiandn-iThe two sections of the rope are cut into several sections to maximize the product of each section of the rope.
  • In other words, the optimal solution of the overall problem depends on the optimal solution of each subproblem.

2.3 Process of dynamic programming

  • Since subproblems are repeated in the process of decomposition of large problems, in order to avoid repeated solving of subproblems, we can:
    • The best solution of the small problem is calculated and stored in the order from the bottom up
    • And then on this basis, we can get the optimal solution of the big problem
  • This top-down analysis and bottom-up solution is also a feature of dynamic programming.

2.4 Application in this problem

When applying dynamic programming, we may face several choices at each step.

Subject:

  • The first cut has n minus 1 choices. We could cut another 1,2… Any position of n minus one.
  • Since we didn’t know which position was optimal, we had to try out all the possibilities and then compare the best solution.
  • Let me write it mathematically
    • f(n) = max(f(i), f(n-i))
    • 0 < i < n

code

func cuttingRope(_ n: Int) -> Int {
    if n < 4 {
        return n - 1
    }
    var dp = [Int](repeating: 1, count: n + 1)
    for i in 3.n {
        for j in 2..<i {
            dp[i] = max(dp[i], max(j * (i - j), j * dp[i - j]))
        }
    }
    return dp[n]
}
Copy the code
Time complexity Spatial complexity
O(n^2) O(n)

Three, greedy algorithm

Greedy algorithms are not the same as dynamic programming. When we apply a greedy algorithm to a problem, at every step we can make a greedy choice, based on which we are sure to get the best solution.

As to why such a greedy choice can lead to the optimal solution. And that’s where the math comes in.

3.1 Application

  • If the length of the string is greater than 5, cut a piece of string of length 3 each time.
  • If the remaining length is still greater than 5, then cut a piece of string of length 3.
  • cycle
  • Until the length of the rope is less than 5.
    • When the length of the string is 4, cut it 2×2=4
    • When the length of the string is 3, cut it to 1×2=2
    • When the length of the string is 2, cut it to 1×1=1
      • Actually do not cut the largest, but the request at least cut a knife that cut bai 🤷♂️

Cutting a piece of string of length three is the greedy choice we make at every step.

3.2 Prove the correctness of the above thought

  • When n > = 5
    • 2(n-2)>n && 3(n-3)>n
    • So if the length of the string is greater than or equal to 5, we can cut it into segments of 3 or 2
  • When n > = 5
    • 3(n-3)>=2(n-2)
    • So we want to cut as many lengths of three as we can

Above is the explanation in the original book, more detailed professional proof ->Krahets

code

func cuttingRope(_ n: Int) -> Int {
    if n < 2 {
        return 0
    }
    if n = = 2 {
        return 1
    }
    if n = = 3 {
        return 2
    }
        
    // The maximum number of segments of length
    var threeCount = n / 3
     
    // You can't cut 3 lengths of string when there are 4 left. It is better to cut 2 lengths of string because 2x2 is more than 3x1
    if n - threeCount * 3 = = 1 {
        threeCount - = 1
    }
    let twoCount = (n - threeCount * 3) / 2
    
    return Int(truncating: NSDecimalNumber(decimal: pow(3, threeCount))) * Int(truncating: NSDecimalNumber(decimal: pow(2, twoCount)))
}
Copy the code
Time complexity Spatial complexity
O(1) O(1)