本文主要是介绍poj 动态规划DP - 2533 Longest Ordered Subsequence，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
动态规划经典题：最长上升子序列。
假如我们考虑求A[1],A[2],…,A[i]的最长非降子序列的长度，其中i<N， 那么上面的问题变成了原问题的一个子问题(问题规模变小了，你可以让i=1,2,3等来分析) 然后我们定义d(i)，表示前i个数中以A[i]结尾的最长非降子序列的长度。OK， 对照“入门”中的简单题，你应该可以估计到这个d(i)就是我们要找的状态。 如果我们把d(1)到d(N)都计算出来，那么最终我们要找的答案就是这里面最大的那个。 状态找到了，下一步找出状态转移方程。
为了方便理解我们是如何找到状态转移方程的，我先把下面的例子提到前面来讲。 如果我们要求的这N个数的序列是：
5，3，4，8，6，7
根据上面找到的状态，我们可以得到：（下文的最长非降子序列都用LIS表示）
- 前1个数的LIS长度d(1)=1(序列：5)
- 前2个数的LIS长度d(2)=1(序列：3；3前面没有比3小的)
- 前3个数的LIS长度d(3)=2(序列：3，4；4前面有个比它小的3，所以d(3)=d(2)+1)
- 前4个数的LIS长度d(4)=3(序列：3，4，8；8前面比它小的有3个数，所以 d(4)=max{d(1),d(2),d(3)}+1=3)
OK，分析到这，我觉得状态转移方程已经很明显了，如果我们已经求出了d(1)到d(i-1)， 那么d(i)可以用下面的状态转移方程得到：
d(i) = max{1, d(j)+1},其中j<i,A[j]<=A[i]
用大白话解释就是，想要求d(i)，就把i前面的各个子序列中， 最后一个数不大于A[i]的序列长度加1，然后取出最大的长度即为d(i)。 当然了，有可能i前面的各个子序列中最后一个数都大于A[i]，那么d(i)=1， 即它自身成为一个长度为1的子序列。
#include<stdio.h>
# define MAX 1002
int n;
int data[MAX];
int dp[MAX];void DP(){int i,j,len=0;for(i=1;i<=n;i++){dp[i]=1;for(j=1;j<=i;j++){if(data[j]<data[i] && dp[j]+1>dp[i])dp[i] = dp[j]+1;}if(len<dp[i]) len=dp[i];}printf("%d\n",len);
}
int main(){int i;scanf("%d",&n);for(i=1;i<=n;i++) {scanf("%d",&data[i]);}DP();
}这篇关于poj 动态规划DP - 2533 Longest Ordered Subsequence的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
