Solution:
First of all, let's think about the simplest way: Obviously, for every segment, there will be two possibilities of going to the left or right. Each possibility contains three pieces of information: the leftmost position, the rightmost position, and the current end position.
Therefore, it is natural that we can get all the possibilities based on the remaining state of the previous segment and combining the two possibilities of the current segment. We only need to choose the smallest length from these possibilities.
But we can immediately find that the complexity of the above approach is $2^n$. Obviously will TLE.
Then we noticed that the value of a ranges from 1 to 1000. In this case, it is not difficult for us to think that the final result will not exceed 2000.
Then we can optimize our above approach: because it can only reach 2000 at most, the total of all states will not exceed $2000\times 2000 \times 2000$ (a combination of three information).
So our complexity becomes $a^3 \cdot n$. Although much better than $2^n$, but still TLE.
Let's take a closer look at the status information we record. We found that in fact, the positions of the two ends and the specific position of the current end do not actually need to be recorded. Because all we need is the length of the current segment and the position of the end position relative to the segment.
For example: [2,6,3] (the segment is 2-6, and the final end position is 3) and [4,8,5] actually have the same effect on the result. It can be directly recorded as [4,1] (the length of the segment is 4, and the relative position of the end point is 1).
So we get $a^2 \cdot n$. Already very close, but still TLE.
Finally, we now only have 3 states: i (the i-th segment), the length of the segment, and the relative position of the end point.
So it is not difficult to think of the following dp definition: Let dp[i][j] denote the minimum segment length with the i-th segment and ending at the j-th position from left to right in the segment.
So obviously there are two possible values for the value of dp[i][j]:
1. max(dp[i-1][j-a[i]], j), that is, go to the right from the end point of the previous segment. But it should be noted that when j>dp[i-1][j-a[i]], j should be taken as the result. Because according to the definition of j, obviously the end point of this case is at the far right.
2.dp[i-1][j+a[i]], that is, go to the left from the end point of the previous segment. It should be noted that dp[i][0]. Take a[i]=2 as an example, at this time, dp[i][0] has three possible values: dp[i-1][2], dp[ i-1][1]+1 (going from 1 to the left with 2 steps will make the length of the segment +1) and dp[i-1][0]+2.
Finally, in the implementation, it is recommended to update the value of dp[i+1][j] with dp[i][j], which will be simpler.
Code:
Java
C++
