题解
首先，我们先思考最朴素的做法：显然对于每一个线段来说，都会产生往左或者往右两种可能。每种可能都会包含三个信息：最左端的位置，最右端的位置和当前结束的位置。
因此很自然的，我们根据上一个线段留下来状态，结合当前线段的两种可能，一直递推，就能得到所有的可能性。我们只需要从这些可能性中选择长度最小的即可。
但是我们可以立刻发现，上面这种做法的复杂度是$2^n$的。显然是会TLE的。
接着我们又注意到a的取值范围是1到1000。这样的话，我们不难想到其实最终的结果一定不会超过2000。
那么我们就可以优化我们上面的做法：因为最多只能到2000，所以所有状态的总数不会超过$2000\times 2000 \times 2000$（三个信息的组合）。
于是我们的复杂度变成了$a^3 \cdot n$。虽然远好于$2^n$，但仍然会TLE。
进一步我们来仔细考量我们记录的状态信息。我们发现，其实两端的位置和当前结束的具体位置其实并不需要都记录下来。因为我们需要的只是当前线段的长度以及结束位置相对于线段的位置即可。
举个例子：[2,6,3]（区间是2-6，最后结束位置在3）和[4,8,5]其实对结果的影响是一样的。可以直接记录为[4,1]（区间长度为4，结束点的相对位置为1）。
于是我们得到了$a^2 \cdot n$。已经非常接近，但是仍然会TLE。
最后，我们现在只有3个状态了：i（第i个线段）、线段的长度和结束点的相对位置。
于是不难想到下面的dp定义：令dp[i][j]表示第i个线段，结束在线段中从左往右第j个位置时，最小的线段长度。
于是自然的dp[i][j]的值就有两种取值的可能：
1. max(dp[i-1][j-a[i]], j)，也就是从上个线段的结束点再往右走。但需要注意，当j>dp[i-1][j-a[i]]时，应当直接取j。因为根据j的定义，显然此时已经结束在最右端了。
2.dp[i-1][j+a[i]]，也就是从上个线段的结束点往左走。需要注意的是dp[i][0]，以a[i]=2为例，此时的dp[i][0]有三个可能的值：dp[i-1][2], dp[i-1][1]+1（从1往左再走2步会使线段长度+1）和dp[i-1][0]+2。
这样我们的复杂度就变成了$a\cdot n$。
最后实现过程中，建议用dp[i-1][j]去主动更新dp[i][j]的值，这样会简单一些。
代码
Java
C++