动态规划

动态规划指的是将一个繁杂的问题分解成子问题之后，通过求解子问题的最优解，从而求得整体最优解。

最长上升子序列

问题如下：

输入数据：

输入的第一行是序列的长度N(1<=N<=1000),第一行给出序列的N个整数，这些整数的取值范围在0-10000.

输出要求：

最长上升子序列的长度。

输入样例：

7
1 7 3 5 9 4 8

输出样例：

4

范例代码：

#include<iostream>
#include<algorithm>
using namespace std;
int main() {
    int n;
    cin >> n;
    int maxlen[100];
    int s[100];
    for (int i = 0; i < n; i++)
    {
        cin >> s[i];
        maxlen[i] = 1;
    }
    for (int i = 1; i < n; i++)
    {
        for (int j = 0; j < i; j++)
        {
            if (s[i] > s[j])
            {
                maxlen[i] = max(maxlen[i], maxlen[j] + 1);
            }
        }
    }
    cout << *max_element(maxlen + 1, maxlen + n + 1);
}

讲解： 

  1. int n;
cin >> n;
int maxlen[100];
int s[100];
for (int i = 0; i < n; i++)
{
   cin >> s[i];
   maxlen[i] = 1;
}

    这一部分是输入数据，并且让存储 以当前下标为终点的子序列的个数 的maxlen数组都初始化为1. 

  1. for (int i = 1; i < n; i++)
{
   for (int j = 0; j < i; j++)
   {
       if (s[i] > s[j])
       {
           maxlen[i] = max(maxlen[i], maxlen[j] + 1);
       }
   }
}

    这一部分是正式求解 以当前下标为终点的最长上升子序列 的长度，并且分别存储在maxlen数组内。
    i每往后循环一次，j就要将i之前的数据都循环一遍。
    当s[i]>s[j]时就要求maxlen[j]+1与maxlen[i]之间的最大值进行maxlen[i]的更新。
    注：之所以需要每次都求maxlen[i]和maxlen[j]+1的最大值，而不直接将maxlen[j]+1赋值给maxlen[i]，是因为maxlen[i]之前的更新可能已经使maxlen[i]>maxlen[[j]+1，故 此时maxlen[i]应保持不变。

  1. 最后一部分为输出部分，调用max_element函数输出manlen数组内的最大值。

    注：max_element函数返回值是一个指针
      max_element和max函数需要调用头文件algorithm