这个是用动态规划做的一道题，先学习一下动态规划的概念吧。  

   用动态规划解题，就是要把问题分解为一个个子问题，对子问题进行求解，而子问题又可以继续进行分解，直到一定小的规模。

   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 #include 
     
       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 }