 # DP cut tape to solve the problem

Posted on June 24, 2022, 3:29 a.m. by Bhamini Khalsa
Category: The back-end Tag: The back-end Go

Make writing a habit together! This is the 13th day of my participation in the "Gold Digging Day New Plan · April More Text Challenge". Click here for more details.

# DP concept

This is a common way to solve complex algorithmic problems. It's actually an idea:

• If the problem is complicated, it must be because the numbers involved in the problem are too large.
• Since the numbers involved are too large, we'll reduce them
• Then find the relationship between the reduced value and the original value
• And get to the final answer

# Cut the tape of the problem

This is a title on OJ's website, which basically reads as follows:

Xiao Ming has a piece of tape, length N, he wants to cut the tape, but xiao Ming stipulated that the length after cutting can only be a, B, C of these three kinds (A, B, C may be equal). Xiao Ming can cut whatever he wants as long as the above restrictions are met. Xiao Ming wants to ask: how to cut, so that the final number of tapes is the largest?

# A concrete example

For example, the original length of this tape is 7, xiaoming stipulated that it could only be cut into 5, 5 and 2 lengths.

As you can see from your brain, there is only one way to cut: 5, 2, and the final number is 2.

## Increasing the value affects the complexity

The above example is easy, and that's because at length 7, the human brain calculates very fast.

The complexity has increased quite a bit. Here are the key points:

• Now that we've figured out the length 7, we're going to add the length to that

• For example, length 8, length 8 first scissors, can be cut in two ways: 5 or 2

• So it goes in two directions,

• `Cut 5`become`Length 3 plus length 5`The problem becomes calculation`The length of the three`Then add 1
• `Cut 2`become`Length 6 plus length 2`The problem becomes calculation`The length of the 6`Then add 1
• At this point, if we already know the answer to length 3 or length 6, then we have the answer to length 8.

• Just compare the answers to the above two cuts and take the larger one.

• The point is, the complexity of calculating length 8 becomes the less complexity of length 3 and length 6.

• So length 3 can still be converted to smaller

• Same thing with length 6

## This is an example of how to do it

We first declare a result array to store results of various lengths:

``````var res []int = make([]int, N+1)
Copy the code``````
• Length 1: invalid, discarded :res = -1, stored here for convenience, means that the length cannot be cut.

• Compute length 2: result is 1, storage: res = 1

• Calculation length 3: According to Xiaoming's regulation:

• First cut 5: illegal
• The first cut 2: become`The length of the 1`+ 1, and`The length of the 1`They already calculated that it's illegal, so they discard it, that's why they're storing illegal ones, right`The length of the 1`
• Based on the above two cuts,`The length of the three`To discard or discard illegally:`res = -1`
• And you keep doing that, all the way to length 700

• According to the definition of complexity in the algorithm, the time complexity of this algorithm should be O(N)O(N)O(N), which is good.

• In the calculation, we use a single number to store the answers of various lengths, so the space complexity is also O(N)O(N)O(N).

## Example code (Golang)

``````func cutRibbon(N, a, b, c int) int {
res := make([]int, N+1)
cons := []int{a, b, c}
//
three := []int{0.0.0}
for idx := 1; idx = N; idx++ {
three, three, three = 0.0.0 / / to empty
for jdx, onecon := range cons {        // iterate over the first cut
if idx  onecon { / / cut
continue
}
if idx == onecon { // Just the same
three[jdx] = 1
continue
}
if res[idx-onecon] == 0 { // Illegal cutting method
continue
}
three[jdx] = res[idx-onecon] + 1
}
// Finally compare the three cuts and take the larger one
sort.Ints(three)
res[idx] = three}return res[N]
}

Copy the code``````

Notice, for some length, if I can't subtract it at all, I don't set it to -1, I just use the default value 0.

Search
Categories