典型的动态规划

解题思路:

注意事项:

参考代码:

#include<bits/stdc++.h>

using namespace std;

#define maxn 10010

#define mod 1000000007

int n;

int a[maxn];

int dp[maxn];//dp[i]表示前i个元素对应的答案

int main(){

scanf("%d",&n);

for(int i=1;i<=n;i++){

scanf("%d",&a[i]);

}

int maxval,minval;

dp[0]=1;

for(int i=0;i<n;i++){

maxval=0;

minval=12345678;

for(int j=i+1;j>=1;j--){

maxval=max(maxval,a[j]);

minval=min(minval,a[j]);

if(maxval-minval+1==i+1-j+1){

dp[i+1]+=dp[j-1];

dp[i+1]%=mod;

}

}

}

printf("%d",dp[n]);

return 0;

}