2 From Recursion to Dynamic Programming (Part 2)

Course Content#

Three Types of Optimization Methods#

① Optimization of the state transition process

Do not change the state definition, use some special data structures or algorithms to specifically optimize the transition process
Example: Egg Dropping V2

② Optimization of program implementation

The state definition remains unchanged, and the transition process also remains unchanged
For example: 0/1 Knapsack Problem, Coin Problem [Rolling Array]

③ Optimization of state definition

A capability that can only be cultivated through extensive training, optimizing from the source
Example: Egg Dropping V3

【⭐】 State Definition -> Source, Transition Process -> Process, Program Implementation -> Result

In-Class Exercises#

———Dynamic Programming——#

HZOJ-46: Cutting Palindrome#

Sample Input

sehuhzzexe

Sample Output

Idea
- String length is 500,000, be careful of timeout
- Normal Version
  - State Definition [Similar to Longest Increasing Subsequence]
    - $dp[i]$: The minimum number of segments to split the first $i$ characters of the string into palindrome strings
    - The number of segments is easier to understand, equivalent to the minimum number of cuts + 1
  - State Transition
    - $dp[i]=min{dp[j]} + 1\ |\ j<i,\ s[j+1,\ i]\ is\ palindrome$
      - State Set: $dp[j]$, the substring from $j + 1$ to $i$ is a palindrome
      - Decision: $min$
  - Time Complexity: $O(n^2)$, can optimize the transition phase
- Optimized Version — Transition Process
  - Phenomenon: In fact, palindrome strings will be very few
  - Optimization: Pre-store the positions of each palindrome string
    - That is, pre-process to obtain the $mark$ two-dimensional array
      - $mark[i]$ stores the starting coordinates of all palindrome strings ending at position $i$ [may be more than one]
    - Therefore, during the transition process, using the processed $mark$ array can avoid a lot of repeated loop traversals to check for palindromes
  - State Transition Equation 👉 $dp[i]=min{dp[mark[i][j]-1]} + 1\ |\ j<i$
    - Size of State Set: $sizeof(mark[i])$, which is the number of palindromes in that substring
  - Time Complexity: $O(n \times m)$, where $m$ represents the number of palindromes in the string
Code
- Normal Version
  - The string and dp array are offset by one
    - The for loop's $i$, $j$ correspond to the indices of the dp array, while the palindrome check's $i$, $j$ should correspond to the string, hence each -1
  - Initialize $dp[i]$, the current character must be a palindrome [regardless of the number of segments, just ensure it can transition]
    - This is actually the case of $j = i -1$
  - Time Complexity: $O(n^2)$
    - Cannot simply look at the two loops plus palindrome checks, which seems to be $O(n^3)$, must consider from the perspective of amortized time complexity
- Optimized Version
  - 【Note】
    - The $mark$ array is two-dimensional, the first dimension can use vector structure without determining the length of the second dimension [changes with the number of palindromes in the substring], also convenient for adding starting coordinates
    - The starting point of each array index, only the string starts from 0
    - The idea of expanding palindromes is to expand from the center to both sides, considering both odd and even numbers of characters

Knapsack-type Problems: A type of problem [to obtain the maximum return under limited resources / to obtain the maximum return at the least cost]

HZOJ-47: 0/1 Knapsack#

Sample Input

Sample Output

Idea
- The number of items is limited, only two states: select / not select
- State Definition
  - $dp[i][j]$: The maximum value that can be obtained with the first $i$ items and a maximum weight of $j$ for the knapsack
- State Transition
  - $dp[i][j] = max\left{\begin{aligned}&dp[i - 1][j]&\text{not selecting the } i\text{th item}\&dp[i - 1][j - v[i]] + w[i]&\text{selecting the } i\text{th item\end{aligned}\right.$
  - State Set: Not selecting the $i$th item, selecting the $i$th item, a total of 2 states
  - Decision: $max$
  - Note in the problem: $v$ represents weight, $w$ represents value
- Time Complexity: $O(n\times V)$
Code
- V1: How the state is defined is how the program is implemented
  - Pay attention to the starting point of traversal, do not miss states
  - This method is not elegant
- V2: Rolling Array 👉 Space Optimization
  - The $i$ dimension only uses the current row and the previous row's values, so only 2 dimensions are needed
  - In the $i$ dimension, uniformly mod 2
- ⭐V3: Change the dp array in the program to 1D, and the $v$, $w$ arrays to 0D, modify the update order
  - To understand the above code, three questions must be answered:
    - ① Why does the dp array only need one dimension?
    - ② Why are the $v$, $w$ arrays not needed?
    - ③ Why is $j$ in reverse order?
  - Answers:
    - ① The thought is still there, the state definition is still two-dimensional, just an optimization in code implementation
    - ② $i$ represents the number of items, from the previous code, it can be seen that $v$, $w$ only need to focus on the $i$th item, so one item can be read in and processed
    - ③ First understand the first question, the state transition code must ensure that the indices of $dp[j]$, $dp[j-v]$ in the [number of items] dimension are $i - 1$; if in order, the index corresponding to $dp[j-v]$ has already changed to $i$, and $dp[i-1][j-v]$ has already been lost
  - ❗ Here, the range of $j$ has changed from the previous $1\to V$ to $V\to v$
    - This is because the values not traversed from $v\to 1$ do not need to change, they can remain [dp is one-dimensional]
    - And the previous code only copied the values of the $i-1$ dimension over [dp is two-dimensional, otherwise it would be initialized to 0]

HZOJ-48: Complete Knapsack#

Sample Input

Sample Output

Idea
- State Definition [Similar to 0/1 Knapsack]
  - $dp[i][j]$: The maximum value that can be obtained with the first $i$ types of items and a maximum weight of $j$ for the knapsack
- State Transition
  - $dp[i][j] = max\left{\begin{aligned}&dp[i - 1][j]&\text{not selecting the } i\text{th type}\&dp[i][j - v[i]] + w[i]&\text{selecting several of the } i\text{th type\end{aligned}\right.$
  - ❗ Note the second type of transition state, regardless of how many of the $i$th type of items are selected, the number of item types is still the first $i$ types, because there are infinite items available for each type, which is the biggest difference from the previous question, somewhat like the coin problem above
    - Here, just make space for one of the $i$th type of items
- Time Complexity: $O(N \times V)$
Code
- The order of updating the table is opposite to the third implementation method of the 0/1 knapsack, must traverse $j$ in order, understanding the above [❗] can help understand this

HZOJ-49: Multiple Knapsack#

Sample Input

Sample Output

Idea
- Normal Version
  - 🆒 Problem Model Transformation: Treat each type of item as multiple independent items, thus transforming it into a 0/1 knapsack problem
  - State Definition and State Transition are consistent with 0/1 Knapsack
  - State Definition
    - $dp[i][j]$: The maximum value that can be obtained with the first $i$ items and a maximum weight of $j$ for the knapsack
  - State Transition
    - $dp[i][j] = max\left{\begin{aligned}&dp[i - 1][j]&\text{not selecting the } i\text{th item}\&dp[i - 1][j - v[i]] + w[i]&\text{selecting the } i\text{th item\end{aligned}\right.$
  - Time Complexity: $O(n\times V\times s)$, can be optimized
- Optimized Version — Targeting the Transition Process ⭐
  - Use Binary Splitting Method to reduce the number of times the same item is traversed
  - Essentially, for a certain type of item, we need to decide how many items to select to get the optimal answer
  - Example: 1 type of item has 14 pieces
    - Normal single splitting method — requires 14 rounds, enumerating all situations of selecting $1 \sim s$ pieces of a certain type of item
    - Binary splitting method — only requires 4 rounds, splitting the 14 items into 1, 2, 4, and 7 pieces to form four piles
      - Can achieve the same effect, and the number of splits will be less
      - Each time the number of splits is double the previous pile, if not enough to split, just put the remaining all
    - Comparison of the number of splits for $s$ items: Normal splitting method: $s$ pieces; Binary splitting method: $log\ s$ pieces
  - Time Complexity: $O(V\times \sum_{i=1}^{n}{logs_i})\approx O(n \times V\times log\ s)$
  - [PS] Can only use binary splitting
    - For each pile of items, there are only select or not select two states, because in the transition process, there are only two results: select or not select
    - So cannot use other bases
- Optimal Time Complexity: $O(n \times V)$ — with the help of monotonic queues, to be discussed later
Code
- V1: Treat it as a 0/1 knapsack problem
  - Time efficiency is not high
- V2: Optimize the transition process
  - Use the binary splitting method
  - Splitting in powers of two, from small to large, can traverse all situations
  - Consider the number of items $k$ in the transition equation

HZOJ-50: Egg Dropping#

Sample Input

2 100

Sample Output

Idea
- 【Exploration Idea】
  - Interpret the requirement: the minimum number of tests in the worst case
    - The number of tests is related to the testing method
    - The worst case indicates the worst luck during the testing process
    - 👉 Best strategy, worst luck
  - Example: 2 eggs, building height of 100
    - Binary method: definitely timeout, limited number of eggs
      - [Worst case]
      - First egg tests at height 50, it breaks
      - The second egg can only test from the first floor up
      - Ultimately requires 50 tests [worst case → hardness is 49]
    - Custom strategy: test every 10 floors
      - [Worst case]
      - 10, 20, 30, ..., 100, when at 100 the egg breaks
      - Then test 91, 92, ..., 99
      - Ultimately requires 19 tests [hardness is 99]
    - Assume the number of tests is $x$
      - [Worst case, the floors that can be tested are as follows, ensuring the number of tests is $x$]
      - First: $x$
      - Second: $x + (x - 1)$
      - Third: $x + (x - 1) + (x - 2)$
      - Finally: $x + (x - 1) + (x - 2) + ... + 1$, adding to 1 is to maximize the number of floors that can be tested, i.e., the optimal strategy
      - Calculate the sum of the arithmetic series: when $(x + 1) \times x \div 2>=100$, the value of $x$ is 14
      - It can be seen: 2 eggs testing 100 floors, at most requires 14 tests
  - Inspiration: In the case of fixed testing times, discover testing strategies
- V1: Normal Version
  - State Definition
    - $dp[i][j]$: The minimum number of tests in the worst case using $i$ eggs to test $j$ floors
  - State Transition
    - $dp[i][j] = min_k(max\left{\begin{aligned}&dp[i - 1][k - 1]+1&\text{egg breaks}\&dp[i][j - k]+1&\text{egg does not break}\end{aligned})\right.$
    - $k$: throw the egg from the $k$th floor
    - $max$: worst luck
    - $min$: minimum number of tests [enumerate all $k$, take the minimum]
    - Decision: reflected in taking the maximum value among the two states, taking the minimum value among all corresponding results for all floors
  - This method has the correct thought but has obvious space and time limitations, see code — V1 for details
- V2: Optimize the transition process
  - In version V1, there are 3 layers of loops, but the process of finding min for $k$ can be optimized to 2 layers of loops
  - ① Fix the number of eggs $i$, the number of floors $j$, observe the relationship between $k$ and $dp[i - 1][k - 1]$, $dp[i][j - k]$
    - The former $dp[i - 1][k - 1]$ is positively correlated with $k$, while the latter $dp[i][j - k]$ is negatively correlated with $k$
    - And to find min(max()), as shown in the figure, the value of the two must be taken as max, so the intersection point of the two is the optimal $k$ value
    - 👉 The optimal transition $k$ value must occur near the intersection of the two functions [PS: the value of $k$ is discrete]
  - ② Fix the number of eggs $i$, then observe the relationship between the number of floors $j$ and the optimal $k$
    - As the number of floors $j$ increases, the green line is unaffected, while the red line shifts up overall, the optimal $k$ value will also shift up
    - To be precise, $k$ will not decrease at least, because the value of $k$ is discrete, the number of floors $j$ must increase within a certain range for $k$ to increase, the total number of tests will increase [the curve corresponding to $k$ is step-like]
  - Combining the two conclusions
    - Suppose the optimal solution corresponding to $dp[i][j-1]$ is $k_1$, then the optimal solution corresponding to $dp[i][j]$ is $k_2\geq k_1$ [must]
      - And $k_2$ must still satisfy the condition $dp[i-1][k_2-1]\leq dp[i][j-k_2]$ [condition ①]
    - If satisfied, $k_2$ must be the maximum value that meets this condition, because $k$ can increase at most by one
    - Therefore, increasing one floor, $k_2$ can either increase by one or remain the same【⭐】
      - $k_2= \left{\begin{aligned}&k_1+1&dp[i-1][k_1]\le dp[i][j-k_1 - 1]\&k_1&\text{otherwise}\end{aligned}\right.$
      - If $k_2=k_1+1$ satisfies condition [①], then $k_2=k_1+1$
  - Essentially, the optimization is about finding the min process, the time complexity has undergone a qualitative leap, see code — V2 for details
- V3: Optimize State Definition
  - Redefine the state
    - Let the original state definition $dp[i][j] = x$, where $x$ represents the minimum number of tests at most
    - Analysis: The storage space required for the original state definition is related to the number of floors $j$, and the value range of $j$ is very large, the array cannot accommodate it; on the other hand, the value range of $x$ is small, for example, when $i = 2$, $x \le \sqrt{2j}$ [square root relationship]
    - Technique: When discovering a correlation between a certain independent variable and dependent variable, the two can be interchanged
    - ⭐ Redefinition: $dp[i][x] = j$, the maximum number of floors that can be tested with $i$ eggs thrown $x$ times
  - State Transition
    - $dp[i][x] = dp[i][x - 1] + dp[i - 1][x - 1] + 1$
    - The maximum number of floors that can be tested = above [not broken] + below [broken] + 1
    - Note: The meaning of the elements in the dp array has changed to the number of floors
    - At this point, it is no longer a dynamic programming problem, but a recursive problem, with no decision-making
  - Finally, find the first $x$ such that $dp[n][x]≥m$ [the given number of floors], which is the answer
  - 🆒 Finally solved the space and time limitations of version V1
  - [PS] If the value ranges are not significantly different, the conversion is meaningless; if no related variables can be found, there is no way to convert
- Note: All transition formulas are for the case of at least 2 eggs, so remember to initialize the case of 1 egg
Code
- V1
  - For finding the extreme value within a range, generally need to initialize an extreme value
  - Space Limitation
    - The storage space used by this program is strongly related to the number of floors
    - Since the number of floors reaches $2^{31}$, this state definition cannot meet the requirements
    - 👉 Needs to optimize the state definition
  - Time Limitation
    - Time Complexity: $O(n \times m^2)$
    - When $m$ is too large, the time consumption is significant
  - [PS] The first dimension of the dp array can be compressed using a rolling array, but the breakthrough for compressing the second dimension is not here
- V2: Optimize the transition process
  - 【Key】 Based on the inflection point conclusion, determine whether the optimal $k$ corresponding to the number of eggs $i$ and the number of floors $j$ can be +1
  - Time Complexity -> $O(n \times m)$
  - [Personal Thought] Here, the inflection point conclusion can actually also be satisfied by the minimum value of $dp[i-1][k-1]\ge dp[i][j-k]$ (let this value be $k_2$, compared to the maximum value $k_1$ of $dp[i-1][k-1]\le dp[i][j-k]$, $k_2=k_1+1\ or\ k_2=k_1$), because the curves of the two (step-like) are symmetric (because if the 34th line were changed to $dp[i - 1][k] <= dp[i][j - k]$, it would have the same effect on OJ), so it is speculated that if $k_2=k_1+1$, then $dp[i-1][k_2-1]=dp[i-1][k_1-1]+1$ at the same time, $dp[i][j-k_2]=dp[i][j-k_1]-1$, so the sought answer $max{dp[i-1][k_2-1],\ dp[i][j-k_2]} + 1$ remains unchanged
    - In fact, it is indeed symmetric, which can be proven by mathematical induction
- V3: Optimize the state definition
  - Has transformed into a recursive problem, dp[][]->f[][]
  - The f array uses long long type, although the maximum number of floors is $2^{31}$, within the int range; but the maximum number of eggs is 32, corresponding to the number of floors exceeding int, which may cause undefined behavior
  - The size of the second dimension of the f array is set to 70000, because when there are 2 eggs and the number of floors is $2^{31}$, the corresponding $x$ value is $65536=2^{16}=\sqrt{2^{31}\times 2}$
  - Program Optimization: Change to rolling array storage; can estimate the size of the second dimension of the f array based on the number of floors, dynamically allocate the array, because it does not need to open such a large size of 70000 each time
  - [PS] Can also use recursion + memoization to implement

HZOJ-44: Longest Increasing Subsequence#

Sample Input

10
3 2 5 7 4 5 7 9 6 8

Sample Output

Idea
- Normal Version
  - The longest strictly increasing subsequence that can be selected [does not need to be continuous]
  - State Definition
    - $dp(i)$: Represents the length of the longest strictly increasing subsequence ending with the element at index i
    - Must end with i!
  - State Transition
    - $dp(i) = max{dp(j)} + 1\ |\ j<i,\ val(j) < val(i)$
    - All states that can transition to $dp(i)$: those satisfying $j<i,\ val(j)<val(i)$ condition, a total of i
    - Decision: $max$
  - Final Answer: $max(f(i))$, take the maximum value among all $dp(i)$
  - Time Complexity of State Transition: $O(n^2)$
- Optimized Version — Transition Process
  - ⭐ Add a $len$ array, where $len[i]$ represents the minimum value at the end of a [strictly increasing] sequence of length $i$
  - State Transition
    - Introduce
      - Referring to the $len$ array in the above figure, in fact, $i$ represents the length, and $min$ represents the minimum value at the end
      - Consider: When there is a new $val[i]=5$, which value should it best attach to in the $len$ array?
        
        ① First, it needs to satisfy that the end value of the sequence is less than it 👉 $len[k] \lt val[i]$
        
        ② Then, the longer the sequence length, the better 👉 the position $i$ should be as large as possible
      - Conversion: Find the index $k_{last}$ of the last value in the $len$ array that is less than $val[i]$, then +1 gives the position to attach; and update the value of $len[k_{last} + 1]$ to $val[i]$, because before the update, $val[i]\le len[k+1]$ must hold, otherwise $k_{last}$ would not be the last one
      - That is: $dp[i]=k_{last}+1\ |\ len[k] \lt val[i]$, involving special binary search11110000
    - In fact, it is equivalent to finding the first value greater than or equal to $val[i]$ 👇
      - $dp[i]=k_{first}\ |\ len[k] \ge val[i]$, involving special binary search 00001111, then update $len[k_{first}]=val[i]$ can do
      - More concise, the subsequent code is implemented this way
  - The prerequisite for binary search is the monotonicity of the $len$ array
    - Proof: The $len$ array must be monotonic, that is to prove
    - ① Initially monotonic
      - Initially set to 0, ∞, ∞
    - ② Assume it is monotonic before the update, it remains monotonic after the update
      - Update operation: $len[k]=val[i]$
      - Before update: $len[k-1] <= len_{original}[k]$
      - After update: $len[k-1] < val[i] =len_{new}[k]<=len_{original}[k]$
    - Therefore, it is monotonic
  - Time Complexity: $O(n\times log\ l)$
    - $l$ represents the length of the longest increasing subsequence, which is also the answer, and is the final effective length of the $len$ array
    - Used binary search to optimize the transition process
  - 【Key】 Maintained a monotonic array, which is strongly related to the sought value, essentially using binary search optimization
Code
- Normal Version
  - The data is large, use scanf instead of cin
  - Note the meaning of the two max
  - Time efficiency of state transition is low
- Optimized Version — State Transition
  - Note the maintenance of the monotonic array, and special binary search0000011111
    - In binary search, ans + 1 represents that each time an element is added, the maximum length increases by at most 1
  - ans represents the index of the last non-maximum value in the len array, which is also the current maximum length of the longest increasing subsequence
  - [PS]
    - No need to open dp, val arrays, only the current state's value is used each time
    - Use memset to set infinity operation: Why programmers like to set INF to 0x3f3f3f3f——Zhihu

——Combining Monotonic Queues/Stacks——#

Based on 3 Monotonic Stacks and Monotonic Queues knowledge points

HZOJ-51: Rectangle#

Sample Input

6 6
0 1 1 1 1 1
1 1 0 1 1 1
1 1 1 1 1 1
1 1 1 0 1 1
1 1 1 1 0 1
1 0 1 1 1 1

Sample Output

Idea
- Recursion + Monotonic Stack
- Note: The result may be too large, take modulo 100007 when outputting
- 【Common Sense】 Top-left coordinate + Bottom-right coordinate 👉 A unique small rectangle
- Problem Transformation: First, for a row, when the bottom-right coordinate falls on a certain point in that row, find the number of valid sub-rectangles that can be formed [the number of valid top-left coordinates corresponding to that point gives the number of sub-rectangles]; then accumulate the number of all points
- By observation, the above sub-problem can be further divided into two parts
  - First, find the nearest position $i$ to the left of point $x$ that is less than the height of $x$ [count the number of consecutive white squares upwards]
  - Then, the state definition of the number of valid sub-rectangles that can be formed with $x$ as the bottom-right coordinate $f(x)$ satisfies 👇
  - Recursion Formula $f(x) = f(i) + h_x\times (x - i)$
    - The number of sub-rectangles that can be formed with $i$ as the bottom-right corresponds to the number of valid top-left coordinates, and these coordinates can also serve as valid top-left coordinates for point $x$
    - That is: the number of valid rectangles in the left part $f(i)$ + the number of valid rectangles in the right part $h_x\times (x - i)$
  - Since we need to find the nearest smaller value $i$ for $x$, we need to use a monotonic stack
- [Inspiration] When there is a need to find the nearest greater or smaller value, one should think of a monotonic stack [generally combined with other algorithms]
Code
- Places where arrays are needed: monotonic stack, rectangle height, recursive state
- Note: Leave a virtual board, initialize recursive state values, initialize stack bottom
- Conventional monotonic stack routine: maintain monotonicity → take value → enter stack
- [PS] Take modulo twice: to prevent the sum of $f[j]$ and $ans$ from exceeding the range without taking modulo, in fact, this problem will not exceed; in addition, it cannot prevent $f[j]$ from exceeding [if it occurs], because $f[j]$ has already been calculated

HZOJ-52: Ancient Typewriter#

Sample Input

6 40
3 3 6 5 1 2

Sample Output

Idea
- Dynamic Programming + Monotonic Queue
- State Definition: $dp[i]$ represents the minimum cost to print the first $i$ characters
- State Transition
  - According to the problem: $dp[i]=min{dp[j]+(s_i-s_j)^2+M}\ |\ j<i$, where $s_i$ is the prefix sum $s_i=\sum_{k=1}^ic_k$
    - Enumerate the possible ending position $j$ of the previous segment to find the optimal
  - Time Complexity: $O(n^2)$
- Slope Optimization [⭐ A particularly elegant type of optimization algorithm]
  - ① Analyze the composition of the state transition formula [cost formula]
    - Mainly eliminate mixed terms
  - ② We are actually looking for which state transition is more optimal. Suppose transitioning from $j$ is better than transitioning from $k$, that is, the cost is smaller, then
    - ↓
    - $dp[j] + (s_i - s_j)^2 + M < dp[k] + (s_i - s_k)^2 + M$
    - ↓
    - $dp[j] + s_j^2 - 2s_is_j<dp[k] + s_k^2 - 2s_is_k$
    - ↓
    - $(dp[j]+s_j^2)-(dp[k]+s_k^2)<2s_i(s_j-s_k)$
  - ③ Further transformation, turning it into a slope form
    - Let $f(i)=dp[i]+s_i^2$
    - ↓ 【Slope Relationship (Ⅰ)】
      - $g(j,k)=\frac{f(j)-f(k)}{s_j-s_k}<2s_i$
    - 👉 Slope [treat $s$ as the x-coordinate, $f$ as the y-coordinate]
    - At this point, it transforms into: if the slope relationship (Ⅰ) holds, then transitioning from $j$ is better than from $k$
  - ④ How to further utilize the slope relationship (Ⅰ)? Analyze the following figure, there are points $l$, $k$, and $j$
    - 【This scenario】 The slope of line $lk$ > the slope of line $kj$ [bow-shaped]
    - Analyze the relationship between the slopes of the two and $2s_i$, there are three situations, see the figure for ①, ②, ③
    - Then, by analyzing the slope relationship (Ⅰ): choose which point to transition from to be optimal, see the check mark ✔ in the nine-square grid
    - It can be seen that any optimal state must not include $k$
    - 👉 Among the candidate answers, there must be no bow-shaped
  - ⑤ Ultimately, this process transforms into: ensuring that among candidate states, the slope of the former must be less than or equal to that of the latter [non-bow-shaped]
    - Based on the slope relationship (Ⅰ) and the characteristics of increasing slopes, the optimal transition state is close to the head
      - First, based on the slope relationship (Ⅰ), remove the head-related elements $x_1$, $x_2$ 【dequeue】
      - At this point, the remaining leftmost element is the optimal transition state $x_3$【queue head】
      - When a new state $x_6$ is added: based on the bow-shaped principle, first eliminate the non-candidate states $x_4$, $x_5$ at the tail, then add $x_6$【maintain monotonicity + enqueue】
    - 👉 That is, maintain a 【monotonic queue】 to keep track of the minimum value in an interval
  - Time Complexity: $O(n)$
Code
- The key lies in the slope optimization idea, pay attention to the use of the slope relationship (Ⅰ) formula and slope comparison (bow-shaped judgment)
- Transforming into a monotonic queue problem: dequeue → take value → maintain monotonicity → enqueue
  - The order of operations is adjusted according to the problem statement
- [PS]
  - With the idea of slope optimization, one can directly apply the formula
  - There is no need to store an array of character cost values, only the prefix sum information is needed

Tips#

Knowledge has no boundaries; with university, there are boundaries