数组切分 动态规划

解题思路:

注意事项:

参考代码:

#include<bits/stdc++.h>

using namespace std;

typedef long long ll;

const int N=1e5+10;

int mod=1e9+7;

int a[N],dp[N];

int main()

{

  int n;cin>>n;

  for(int i=1;i<=n;i++)cin>>a[i];

  dp[0]=1;

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

  {

    int minn=1e9,maxn=0;

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

    {

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

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

       if(maxn-minn+1==i-j+1)

       {

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

        dp[i]%=mod;

       }

    }

  }

  cout<<dp[n]<<endl;

  return 0;

}