这个是用动态规划做的一道题，先学习一下动态规划的概念吧。
用动态规划解题，就是要把问题分解为一个个子问题，对子问题进行求解，而子问题又可以继续进行分解，直到一定小的规模。
DP与递归类似，但递归会导致重复计算，而用DP每次计算后的子问题的解都会被保存起来，从而避免了重复计算，保证了效率，比如本题用maxlen[]保存每个状态值
对于每组与子问题有关系的变量，我们对他们进行取值，称之为子问题的“状态”，而“状态”的值就是该子问题的解。
定义出什么是“状态”、得到“状态”的值后，就要找出不同状态之间的迁移关系，即通过一个状态求另一个状态的值，往往有一个递推公式，我们把这个递推公式成为状态转移方程。
现在反过来看这道题：
输入数据
输入的第一行是序列的长度N (1 <= N <= 1000)。第二行给出序列中的 N 个整数，这些
整数的取值范围都在0 到10000。
输出要求
最长上升子序列的长度。
输入样例
7
1 7 3 5 9 4 8
输出样例
4
输入数据
输入的第一行是序列的长度N (1 <= N <= 1000)。第二行给出序列中的 N 个整数，这些
整数的取值范围都在0 到10000。
输出要求
最长上升子序列的长度。
输入样例
7
1 7 3 5 9 4 8
输出样例
4
问题分析：
怎么分解成子问题呢？我们把“以a
k为终点的序列的最长上升子序列的长度”作为问题的子问题，其中k = 1,2,3......N .
这样就把问题分解为N个子问题，只要我们把这N个子问题解决了，从中找出解值最大的即为原问题的解
怎么求状态转移方程呢？显然当k = 1的时候，maxlen[k] = 1;而通过k=1这个状态求别的状态的转移方程则可以写成：
maxlen[k] = (max(maxlen[i])，i = 1,2,3,....,k-1&& str[i] < str[k]) + 1;
这个方程的含义是：要求以a
k为终点的序列的最长上升子序列的长度，只要算出以满足条件的a
k左边的某一个数为终点的序列的最长上升子序列的长度 再 加上a
k这个数，即长度再加1即可，得到的这样一个序列必定是包含a
k的
这里要充分理解递归的思想（虽然这里并不用到递归函数）
1 #include <iostream> 2 using namespace std; 3 4 int str[1001]; 5 int maxlen[1001]; 6 int p[1001]; 7 8 int main() 9 { 10 int N;cin >> N; 11 memset(str,0,sizeof(str)); 12 for(int i = 1;i < N;i++) 13 cin >> str[i]; 14 memset(maxlen,0,sizeof(maxlen)); 15 maxlen[1] = 1; 16 for(int i = 2;i < N ;i++){ 17 int temp = 0; 18 for(int j = 1;j < i;j++){ 19 if(str[j] < str[i]) 20 if(temp < maxlen[j]) 21 temp = maxlen[j]; 22 } 23 maxlen[i] = temp + 1; 24 } 25 int temp = -1; 26 for(int i = 1;i < N ;i++){ 27 if(temp < maxlen[i]) 28 temp = maxlen[i]; 29 } 30 cout << temp; 31 }
本文转自编程小翁博客园博客，原文链接：http://www.cnblogs.com/wengzilin/archive/2012/10/15/2724874.html，如需转载请自行联系原作者
