1问题描述

  设计一个O(n2)时间的算法，找出由n个数组成的序列的最长单调递增子序列。

  输入格式:

  输入有两行： 第一行：n，代表要输入的数列的个数 第二行：n个数，数字之间用空格格开

  输出格式:

 最长单调递增子序列的长度

2算法描述

void solve()
{
   for(int i = 1; i <= n; ++i)
    F[i] = 1;
   for(int i = 1; i <= n; ++i)
   {
       for(int j = 1; j < i; ++j)
       {
           if(a[i] > a[j] && F[i] < F[j] + 1)
            F[i] = F[j] + 1;
       }
   }
   for(int i = 1; i <= n; ++i)
    if(F[i] > max_)
        max_ = F[i];
}

 3问题求解  

  3.1 各数组解释

    int a[1024]; //原数组

    int F[1024]; //在i处的长度

    int n; //目标数组

 3.2 算法思路

    F[i]的含义为：在“可取元素为前i”且“取第i个元素”时最长递增序列的长度。

    列出递归关系为： F[i] = max(F[k]) + 1, 1 <= k <= i - 1 && a[i] > a[k]

    其实就是利用动态规划的一种思想

    采用遍历数组序列，不断更新递增序列的长度以至于来找到最长单调递增序列。

3.3 复杂度分析

    时间复杂度：遍历两个数组，双循环 T=O（n²）

    空间复杂度：O（n）

 4动态规划心得体会

4.1动态规划又叫做填表法

1、自底向上：思想是逆向的，但也能正向解答。两者是相同的，只是求解顺序不一样。

2、状态转移方程：求解动态规划的顺序是先暴力递归——带备忘录的递归——动态规划。递归的递归体就是动态规划的状态转移方程。
3、最优子问题：大问题分成小问题，小问题寻找最优解构成大问题的最优解。

4.2能用动态规划求解问题，常常具备以下特点

1、计数
　　有多少种方式走到右下角
　　有多少种方法选出k个数使得和是Sum
2、求最大最小值
　　从左上角走到右下角路径的最大数字和
　　最长上升子序列长度
3、求存在性
　　取石子游戏，先手是否必胜
　　能不能选出k个数使得和是Sum