This is the 28th day of my participation in the August Challenge
1977. Number of schemes for dividing numbers
Thought analysis
For an obvious dynamic programming problem, it is more important to write the idea of state transition equation than to write the code. Before writing the state transition equation, we need to specify the state representation.
- Numbers require non-decrement and no leading 0, which is obviously a filtering condition. Write it down for later.
- Assuming num= “327154”, given that we have divided 327, what happens when we add 1?
- First of all, 1 can’t be a new word by itself, because neither 327 nor 27 is greater than 1 and does not satisfy diminishing
- Secondly, using the original scheme 327 can definitely meet the requirements. Adding one digit to the last digit will definitely make the number larger, so it will not affect the result
- And finally, we need to think about 32, 71. This kind of new scheme combines 1 with other letters, but in essence, it can be understood as adding 71 after 32. Therefore, we cannot carry out dynamic programming solely from the length of data, but must also consider the position of the last element under a given length
That’s about half the answer
Dp [I][j] represents a string of length j, and the last integer starts with I.
- We can judge from dp[I][j] that the last digit is j-i
- Since the end digit of dp[I][j] starts from I, his scheme must come from dp[k][i-1], where i-1-k > j-i must be illegal and i-1-k < j-i must be legal. If I minus 1 minus k is equal to j minus I, for this way we need to compare the sizes of the two. (Can be pruned by maximum prefix length)
- If the last element is large, it is legal.
- The result is the sum of dp[k][n] (k is any value)