分析
状态定义：\(dp[i][j] | (j \le i)\)表示前\(i\)棵树中，第\(i\)棵树是第\(j\)棵被砍的排列的方案数。
状态转移：根据讨论，如果\(H_i > H_{i+1}\)，则先砍\(H_i\)。如果\(H_i < H_{i+1}\)，则先砍\(H_{i+1}\)。如果\(H_i = H_{i+1}\)，则先砍这两棵树都可以。总之，谁高就先砍谁。
if(H[i] > H[i+1]) \(dp[i+1][j] = \sum_{k=1}^{j-1} dp[i][k]\)，就是第\(i\)棵树只要在第\(i+1\)棵树之前的任何一个位置被砍都是合法的排列方案。
if(H[i] < H[i+1]) \(dp[i+1][j] = \sum_{k=j}^{i}dp[i][k]\) , 就是第\(i\)棵树只能在位置\(j-i\)被砍。这是有一个比较特殊的地方，就是第\(i\)棵树似乎应该在位置\(j+1\)及之后被砍。为什么位置\(j\)也可以呢？
我的理解是：对于第\(i\)棵树是在位置\(j\)被砍的排列，把第\(i+1\)棵树强行安排在位置\(j\)去砍，相当于第\(i\)棵树及后面的树都后移一个位置，得到的排列仍然合法。
if(H[i] == H[i+1]) \(dp[i+1][j] = \sum_{k=1}^i dp[i][k]\), 就是第\(i\)棵树的被砍位置不影响第\(i+1\)棵树的位置。
TLE 代码
#include<bits/stdc++.h>
using namespace std;
#define MAXN 4005
#define MOD (int)(1E9+7)
int h[MAXN];
int dp[MAXN][MAXN];
int n, ans;
int main(){
cin >> n;
for(int i = 1; i <= n; i++) cin >> h[i];
dp[1][1] = 1;
for(int i = 1; i < n; i++){
for(int j = 1; j <= i+1; j++)
if(h[i] == h[i+1])
for(int k = 1; k <= i; k++)
dp[i+1][j] += dp[i][k], dp[i+1][j] %= MOD;
else if(h[i] > h[i+1])
for(int k = 1; k <= j-1; k++)
dp[i+1][j] += dp[i][k], dp[i+1][j] %= MOD;
else
for(int k = j; k <= i; k++)
dp[i+1][j] += dp[i][k], dp[i+1][j] %= MOD;
}
for(int j = 1; j <= n; j++) {
ans += dp[n][j];
ans %= MOD;
}
cout << ans << endl;
}
AC代码，空间未优化
#include<bits/stdc++.h>
using namespace std;
#define MAXN 4005
#define MOD (int)(1E9+7)
int h[MAXN];
long long dp[MAXN][MAXN], sum[MAXN][MAXN];
int n, ans;
int main(){
cin >> n;
for(int i = 1; i <= n; i++) cin >> h[i];
dp[1][1] = sum[1][1] = 1;
for(int i = 1; i < n; i++)
for(int j = 1; j <= i+1; j++) {
if(h[i] == h[i+1])
dp[i+1][j] += sum[i][i], dp[i+1][j] %= MOD;
else if(h[i] > h[i+1])
dp[i+1][j] += sum[i][j-1], dp[i+1][j] %= MOD;
else {
dp[i+1][j] += sum[i][i] - sum[i][j-1], dp[i+1][j] %= MOD;
if(dp[i+1][j] < 0) dp[i+1][j] += MOD;
}
sum[i+1][j] += (sum[i+1][j-1] + dp[i+1][j]) % MOD;
}
for(int j = 1; j <= n; j++) {
ans += dp[n][j];
ans %= MOD;
}
cout << ans << endl;
}