动态规划学习--经典例题（一）

最长不降子列：

解题思路：

              常规思路：

　　　　　　穷举—>从第一个数开始，慢慢往后面去寻找比他大的数，但是会发现，其实这样根本找不到最优的那个解，有时候看似最优，其实不是最优选择，即有后效性。

              正确思路：

　　　　　　确定一个最大的数，从这个数往前找。这样每个数都有一个对应的最长上升子列，到了最后的数，就有了要求的最长上升子列。

              Maxlen[]储存最长上升子列的长度：

 1 /*
 2     递推型动态规划
 3         求最长上升子列
 4         从局部到整体，先确定最大的那个值，之后一步步往回求
 5 
 6 */
 7 
 8 #include
 9 #include
10 #include
11 using namespace std;
12 
13 #define Max 101
14 
15 int main() {
16     int a[Max],maxlen[Max];
17     int n;
18     int i,j;
19     cout<<"请输入数组的长度"<<endl;
20     cin>>n;
21     cout<<"请输入数组的数据"<<endl;
22     for(i=1; i<=n; i++) {
23         cin>>a[i];
24         maxlen[i]=1;
25     }
26     for(i=2; i<=n; i++)
27         for(j=1; j)
28             if(a[j]<a[i]) {
29                 maxlen[i]=max(maxlen[j]+1,maxlen[i]);//可能存在 maxlen[i]比 maxlen[j]+1大，所以要进行比较 
30             }
31     cout<<* max_element(maxlen+1,maxlen+ n + 1);//找出最大值
32     return 0;
33 }