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.

So how about length 700?

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 5becomeLength 3 plus length 5The problem becomes calculationThe length of the threeThen add 1
    • Cut 2becomeLength 6 plus length 2The problem becomes calculationThe length of the 6Then 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] = -1, stored here for convenience, means that the length cannot be cut.

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

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

    • First cut 5: illegal
    • The first cut 2: becomeThe length of the 1+ 1, andThe length of the 1They already calculated that it’s illegal, so they discard it, that’s why they’re storing illegal ones, rightThe length of the 1
    • Based on the above two cuts,The length of the threeTo discard or discard illegally:res[2] = -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[0], three[1], three[2] = 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[2]}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.