2 From Recursion to Dynamic Programming (Part 2)

Course Content#

Three Types of Optimization Methods#

① Optimization of 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 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])$, i.e., 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$ corresponds to the index of the dp array, while the palindrome check for $i$, $j$ must correspond to the string, hence each -1
  - Initialize $dp[i]$, the current character must be a palindrome [regardless of the number of segments, only care about the transition]
    - This is actually the case of $j = i -1$
  - Time Complexity: $O(n^2)$
    - One cannot simply look at the two loops plus the palindrome check, which seems to be $O(n^3)$; one must consider it 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 [according to the number of palindromes in the substring], also convenient to add starting coordinates
    - The starting point of each array index, only the string starts from 0
    - The idea of expanding palindromes, from the center outwards, needs to consider 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^{th} \text{ item}\&dp[i - 1][j - v[i]] + w[i]&\text{selecting the } i^{th} \text{ 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, how the program is implemented
  - Note the starting point of traversal, do not miss the state
  - 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, modifying the update order
  - To understand the above code, one must answer three questions:
    - ① 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 process remains, 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 can read in one item and process one item
    - ③ First understand the first question, the state transition code must ensure that the indices on the right side of the equation $dp[j], dp[j-v]$ in the dimension of [number of items] are $i - 1$; if in forward order, the index corresponding to $dp[j-v]$ has already changed to $i$, while $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 from the $i-1$ dimension [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^{th} \text{ type}\&dp[i][j - v[i]] + w[i]&\text{selecting several of the } i^{th} \text{ 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 each type of item has an infinite number available, 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 problem, need to traverse $j$ in the forward direction, understanding the previous [❗] can help understand this part

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^{th} \text{ item}\&dp[i - 1][j - v[i]] + w[i]&\text{selecting the } i^{th} \text{ 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 pieces to choose 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 pieces into 1, 2, 4, and 7 pieces to form four piles
      - This can achieve the same effect, and the number of splits will be less
      - Each split's quantity is double that of the previous pile, and if it cannot be split, just take the remaining all
    - Comparison of the number of splits for $s$ pieces: 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 of selecting or not selecting
    - Therefore, 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
  - Using the Binary Splitting Method
  - Splitting in powers of two, from small to large, to traverse all situations
  - Consider the number of pieces $k$ in the transition equation

HZOJ-50: Egg Dropping#

Sample Input

2 100

Sample Output

Idea
- 【Exploration Thought】
  - 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]
      - The first egg tests the height of 50, it breaks
      - The second egg can only test from the first floor upwards
      - Ultimately needs to test 50 times [worst case → hardness is 49]
    - Custom strategy: test upwards at intervals of 10 floors
      - [Worst Case]
      - 10, 20, 30, ..., 100, when at 100 the egg breaks
      - Then 91, 92, ..., 99
      - Ultimately needs to test 19 times [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: $(x + 1) \times x \div 2 >= 100$ for the value of $x$, which equals 14
      - It can be concluded: 2 eggs can test 100 floors, at most need to test 14 times
  - Inspiration: In the case of fixed testing times, discover testing strategies
- V1: Normal Version
  - State Definition
    - $dp[i][j]$: Using $i$ eggs, testing $j$ floors, the minimum number of tests in the worst case
  - 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 value]
    - 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 process but has obvious space and time limitations, see code — V1
- V2: Optimize the Transition Process
  - In version V1, there are 3 layers of loops, but the process for finding min for $k$ can be optimized to 2 layers of loops
  - ① Fix the number of eggs $i$, and 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 optimal $k$ value occurs near the intersection of the two
    - 👉 The optimal transition $k$ value must occur near the intersection of the two functions [PS: $k$ values are discrete]
  - ② Fix the number of eggs $i$, then observe the relationship between the number of floors $j$ and the optimal $k$
    - When the number of floors $j$ increases, the green line is unaffected, while the red line shifts upward overall, the optimal $k$ value will also shift upward
    - To be precise, $k$ will not decrease, because $k$ values are discrete, $k$ can only increase when the number of floors $j$ increases within a certain range, the total number of tests will also increase [the curve corresponding to $k$ is stepwise]
  - 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$ still needs to satisfy the condition $dp[i-1][k_2-1]\leq dp[i][j-k_2]$ [①]
    - If satisfied, $k_2$ must be the maximum value that meets this condition, because $k$ can at most increase 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$
  - The essence of the optimization is the process of finding min, and the time complexity has undergone a qualitative leap, see code — V2
- V3: Optimize State Definition
  - State Redefinition
    - 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 represent 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 transformation is meaningless; if no related variables can be found, there is no way to transform
- 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
    - And the number of floors has reached $2^{31}$, so this state definition cannot meet the needs
    - 👉 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 both (stepwise) 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 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 $2^{31}$ floors, 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 there is no need to always allocate such a large 70000
  - [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 selected continuously]
  - 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
    - Introduction:
      - Referencing the $len$ array in the figure, in fact, $i$ represents the length, and $min$ represents the minimum value at the end
      - Consider: When a new $val[i]=5$ comes in, which value in the $len$ array should it best follow?
        
        ① First, it needs to satisfy that the last value of the sequence is smaller than it 👉 $len[k] < val[i]$
        
        ② Then the longer the sequence, the better 👉 the position $i$ should be as large as possible
      - Transformation: 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 insert; and update $len[k_{last} + 1]$ to $val[i]$, because before updating, $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] < val[i]$, involves 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]$, involves special binary search 00001111, then update $len[k_{first}]=val[i]$
      - More concise, and the subsequent code is implemented this way
  - The condition 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 updating, it remains monotonic after updating
      - Update operation: $len[k]=val[i]$
      - Before updating: $len[k-1] <= len_{original}[k]$
      - After updating: $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 that is strongly related to the sought value, effectively using binary search
Code
- Normal Version
  - The data is large, use scanf instead of cin
  - Note the meanings of the two maxes
  - The time efficiency of state transition is low
- Optimized Version — State Transition
  - Note the maintenance of the monotonic array, and special binary search0000011111
    - When performing 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-extreme value in the $len$ array, which is also the current maximum length of the longest increasing subsequence
  - [PS]
    - There is no need to open the dp, val arrays, only the current state value is used each time
    - Use memset to set infinity: Why programmers like to set INF to 0x3f3f3f3f — Zhihu

——Combining Monotonic Queue/Stack——#

Based on 3 Monotonic Stack and Monotonic Queue 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 Knowledge】 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 subproblem can be divided into two parts
  - First, find the position $i$ of the nearest height less than $x$ to the left of point $x$ [count the number of consecutive white squares upwards]
  - Then, the 【State Definition】 for $x$ as the bottom-right coordinate can form valid sub-rectangles $f(x)$ satisfies 👇
  - 【Recursion Formula】 $f(x) = f(i) + h_x\times (x - i)$
    - The number of valid sub-rectangles 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 on the left part $f(i)$ + the number of valid rectangles on the right part $h_x\times (x - i)$
  - Since we need to find the nearest smaller value for $x$, we need to use a monotonic stack
- [Inspiration] When there is a need to find the nearest larger or smaller value, one should think of a monotonic stack [generally combined with other algorithms]
Code
- Areas where arrays are needed: Monotonic Stack, Rectangle Height, Recursion State
- Note: Leave virtual boards, initialize recursion state values, initialize stack bottom
- Conventional monotonic stack routine: Maintain monotonicity → Take value → Enter stack
- [PS] Take modulo twice: to prevent the unmodulated $f[j]$ from exceeding the range when added to $ans$, in fact, this problem will not exceed; moreover, it cannot prevent $f[j]$ from exceeding the range [if it occurs], because $f[j]$ has already been calculated

HZOJ-52: The Old Typing Machine#

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 of printing 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 of printing, find the optimal one
  - 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 better. 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 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 [taking $s$ as the horizontal coordinate, $f$ as the vertical 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$
    - 【Scene Here】 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 cases, see the figure for ①, ②, ③
    - Then analyze using the slope relationship (Ⅰ): choose which point to transition from is optimal, see the checkmark in the nine-square grid ✔
    - It can be seen that any optimal state must not include $k$
    - 👉 Among the candidate answers, there must not be any bow-shaped
  - ⑤ Ultimately, this process transforms into: ensuring that among candidate states, the slope of the former must be smaller than or equal to that of the latter [non-bow-shaped]
    - Based on the slope relationship (Ⅰ) and the characteristics of increasing slopes, the sought 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 to maintain a 【monotonic queue】, maintaining a 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
- [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