题意：你面前有宽度为1，高度给定的连续木板，每次可以刷一横排或一竖列，问你至少需要刷几次。

思路：先逆推，dp[i][j]表示第i列以后的木板都刷完了（不包括第i列）且前面的第j列是横着刷的（且假设它能够刷到后面的第i+1列），那么第i列之后不包括第i列最少需要的次数。所以当value[j]>=value[i]的时候第i列就不用刷了。

尽管这种做***出现一些不合法的情况，但是最后的推出的结果运用到的必然都是合法的情况。

我们再正着看。

最后的答案应该是dp[0][0]，因为第0列是横着刷的就相当于没刷，第0列以后的都刷完了，就相当于刷完所有的。

它的来源是min(dp[1][0]+1,dp[1][1]+value[1])，即第一列是竖刷和第一列全为横刷的情况。剩下的依次类推。

#include <bits/stdc++.h>
using namespace std;
const int maxn = 5005;
int dp[maxn][maxn], a[maxn];
int main() {
    int n;
    cin >>n;
    for (int i = 1; i <= n; i++) cin >> a[i];
    for (int i = n; i >= 1; i--) {
        for (int j = 0; j < i; j++) {
            if (a[j] >= a[i]) {
                dp[i - 1][j] = dp[i][i];
            } else {
                dp[i - 1][j] = min(dp[i][j] + 1, dp[i][i] + a[i] - a[j]);
            }
        }
    }
    cout << dp[0][0] << endl;
    return 0;
}