[Go] sword finger offerJZ14 cut the rope

“This is the 19th day of my participation in the First Challenge 2022, for more details: First Challenge 2022”.

1. Title Description

You are given a string of length n, please cut the string into m segments (both m and n are integers, n > 1 and m > 1, m <= n), and write the length of each segment as K [1]… , k [m]. Excuse me [1] [2] k k… What is the largest possible product of k[m]? For example, when the length of the rope is 8 and we cut it into three lengths of 2, 3 and 3, the maximum product we get is 18.

Data range: 2≤ N ≤60 Advanced: space complexity O(1), time complexity O(n)

Second, the problem solving

The problem is an optimal solution problem, given a length, we are required to give the maximum product segmentation; At the same time, both the length and the partition length are integers greater than 1, so some partial cases can be excluded.

① Dynamic programming

Since finding a new maximum product can be obtained by transferring the maximum product under the previous smaller length after cutting a piece of rope into two pieces, dynamic programming can be used to solve the problem.

First, we create an array dp to store the largest product of length n, and we get dp[2] = 1.

Cutting a piece of string of length 1 contributes nothing to the maximum product and consumes the total length of the string, so we don’t take into account the case of cutting length 1 (a special piece of string of length 2 has to be cut two pieces of length 1).

Let’s say we cut a piece of string of length J from a piece of string of length I, and the product is j times I minus j, and then we have the choice to continue cutting or stop cutting, and if we need to continue cutting, the length is j times dp[I minus j]. Therefore, the state transition equation is obtained; Dp [I] = Max (dp [I], Max (j * (I – j) and dp (I – j] j *)).

The final result is dp[n].

func cutRope( number int ) int {
    // write code here
    dp := make([]int, number + 1)
    for i := 3 ; i <= number; i++ {
        for j := 2; j <= i; j++ {
            dp[i] = max(dp[i], max(j * (i - j), j * dp[i - j]))
        }
    }
    return dp[number]
}

func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}
Copy the code

(2) induction

By analogy with the area of a rectangle and a square, the product is greatest when the numbers are the same, e.g. 2 * 4 < 3 * 3 * 3 < 1 2 * 2

Then the value of 3 will be higher if it occurs more frequently in the number of rope segments. For example, here are some examples:

We can find that the maximum product is to take as many 3 as possible, and then judge the n remainder 3. If the remainder is 0 or 2, it is a more reasonable case, and can be divided according to the above method. But if the remainder is 1, since 1 doesn’t contribute to the largest product, adding it to one of the 3’s makes it 4, which makes the product even bigger. (To simplify the code, consider the 4 a product of two twos.)

func cutRope( number int ) int {
    // write code here
    // Returns the special value
    if number < 2 {
        return 0
    }
    if number == 2 {
        return 1
    }
    if number == 3 {
        return 2
    }
    
    threeNum := number / 3
    if number % 3= =1 {
        threeNum--
    }
    twoNum := number % 3 / 2
    return int(math.Pow(3.float64(threeNum))*math.Pow(2.float64(twoNum)))
}
Copy the code