动态dp法

[原题]https://www.acwing.com/problem/content/description/897/

(动态规划) O(n2)O(n2)
状态表示：dp[i]表示从第一个数字开始算，以num[i]结尾的最大的上升序列。(以num[i]结尾的所有上升序列中属性为最大值的那一个)

状态计算（集合划分）：j∈(0,1,2,..,i-1), 在num[i] > num[j]时，
dp[i] = max(dp[i], dp[j] + 1) // dp[j]+1->前一个小于自己的数结尾的最大上升子序列加上自己，即+1
有一个边界，若前面没有比i小的，dp[i]为1（自己为结尾）。

最后在找dp[i]的最大值。

时间复杂度
O(n2)O(n2) 状态数(nn) * 转移数(nn)

//动态dp板子 .cpp 

#include <iostream>
#include<vector>
#include<cstdio>
#include <algorithm>
#include<cstring>

using namespace std;
typedef long long ll;
#define INF 0x3f3f3f3f

const int N = 1010;
int num[N], dp[N];

int main()
{
    int n;
    cin >> n;
    int i, j;
    for (i = 0; i < n; i++)
    {
        cin >> num[i];
    }

    int mx = 1;
    for (i = 0; i < n; i++)
    {
        dp[i] = 1;//默认为1，找不到前面的数字小于自己的时候就为1；
        for (j = 0; j < i; j++)
        {
            if (num[i] > num[j])
                dp[i] = max(dp[i], dp[j] + 1); //动态dp板子
        }
        mx = max(mx, dp[i]);
    }
    cout << mx << endl;
    return 0;
}

基于优化目的

动态dp+二分法

1.状态表示：dp[i]表示长度为i的最长上升子序列，末尾最小的数字。(长度为i的最长上升子序列所有结尾中，结尾最小min的) 即长度为i的子序列末尾最小元素是什么。

2.状态计算：对于每一个num[i], 如果大于dpcnt-1，那就cnt+1，使得最长上升序列长度+1，当前末尾最小元素为num[i]。 若num[i]小于等于dp[cnt-1],说明不会更新当前的长度，但之前末尾的最小元素要发生变化，找到第一个 大于或等于 (这里不能是大于) num[i]，更新以那时候末尾的最小元素。

3.dp[i]一定以一个单调递增的数组，所以可以用二分法来找第一个大于或等于num[i]的数字。

时间复杂度
O(nlogn)O(nlogn) 状态数(nn) * 转移数(lognlogn)

//动态dp板子 .cpp 

#include <iostream>
#include<vector>
#include<cstdio>
#include <algorithm>
#include<cstring>

using namespace std;
typedef long long ll;
#define INF 0x3f3f3f3f

const int N = 1010;
int num[N], dp[N];

int main()
{
    int n,cnt=0;
    cin >> n;
    int i, j;
    for (i = 0; i < n; i++)
    {
        cin >> num[i];
    }

    dp[cnt++] = num[0];
    for (i = 1; i < n; i++)
    {
        if (num[i] > dp[cnt - 1])
            dp[cnt++] = num[i];
        else
        {
            int left = 0,right = cnt - 1;
            while (left < right)
            {
                int mid = (left + right) >> 1;
                if (dp[mid] >= num[i])
                    right = mid;
                else
                    left = mid + 1;
            }
            dp[right] = num[i];
        }
    }
    cout << cnt << endl;
    return 0;
}

[482. 合唱队形]https://www.acwing.com/problem/content/484/

#include <iostream>
#include<vector>
#include<cstdio>
#include <algorithm>
#include<cstring>

using namespace std;
typedef long long ll;
#define INF 0x3f3f3f3f

const int N = 110;
int num[N] = { 0 }, dp1[N] = {0}, dp2[N] = {0};


int main()
{
    int n;
    cin >> n;
    int i, j, k;

    for (i = 0; i < n; i++)
    {
        cin >> num[i];
    }

    for (i = 0; i < n; i++)
    {
        dp1[i] = 1;//默认为1，找不到前面的数字小于自己的时候就为1；
        for (j = 0; j < i; j++)
        {
            if (num[i] > num[j])
                dp1[i] = max(dp1[i],dp1[j] + 1); //动态dp板子
        }
    }

    for (i = n - 1; i >= 0; i--)
    {
        dp2[i] = 1;
        for (j = n - 1; j > i; j--)
        {
            if (num[i] > num[j])
                dp2[i] = max(dp2[i], dp2[j] + 1);
        }
    }
    int mx = 1;
    for (k = 0; k < n; k++)
        mx = max(mx, dp1[k] + dp2[k] - 1);

    cout << n - mx << endl;
    return 0;
}