给定一组数列:a1,a2,...an;
求该数列的最长的递增长度?
解法:动态规划
状态转移方程:dp[i]=max(dp[i],dp[j]+1)
code:
int dp[maxn],a[maxn],m;
cin>>n;
dp[1]=1;
for(int i=1;i<=n;++i)
{
cin>>a[i];
for(int j=i-1;j>0;--j)
{
if(a[j]<a[i]) {dp[i]=max(dp[i],dp[j]+1);}
}
if(dp[i]==0) dp[i]=1;
m=max(m,dp[i]);
}
解释状态转移方程:
1.顺序问题:有两个顺序:
一、输入数列的顺序,1~n
二、递推的顺序:n1(也可以是1n,这不影响,因为我们的递推每次都取最大值)