这个是用动态规划做的一道题，先学习一下动态规划的概念吧。
用动态规划解题，就是要把问题分解为一个个子问题，对子问题进行求解，而子问题又可以继续进行分解，直到一定小的规模。
DP与递归类似，但递归会导致重复计算，而用DP每次计算后的子问题的解都会被保存起来，从而避免了重复计算，保证了效率，比如本题用maxlen[]保存每个状态值
对于每组与子问题有关系的变量，我们对他们进行取值，称之为子问题的“状态”，而“状态”的值就是该子问题的解。
定义出什么是“状态”、得到“状态”的值后，就要找出不同状态之间的迁移关系，即通过一个状态求另一个状态的值，往往有一个递推公式，我们把这个递推公式成为状态转移方程。
现在反过来看这道题： 输入数据 输入的第一行是序列的长度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 #include2 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 }