C++动态规划暴力 | #合唱队#

#include <iostream>
#include <vector>
using namespace std;

int minP(vector<int> arr, int N) {
    vector<int> dp1(N, 1);
    vector<int> dp2(N, 1);
    for(int i = 1; i < N; i++){
        for(int j = 0; j < i; j++){
            if(arr[j] < arr[i]){
                dp1[i] = max(dp1[j]+1, dp1[i]);
            }
        }
    }
    for(int i = N - 2; i >= 0; i --){
        for(int j = N - 1; j > i; j--){
            if(arr[j] < arr[i]){
                dp2[i] = max(dp2[j]+1, dp2[i]);
            }
        }
    }

    int max = 0;
    for(int i = 0; i < N; i++){
        max = max > (dp1[i] + dp2[i] - 1) ? max : (dp1[i] + dp2[i] - 1);
    }

    return N - max;
}

int main() {
    int N;
    cin >> N;
    vector<int> arr(N, 0);

    for (int i = 0; i < N; i++) cin >> arr[i];

    cout << minP(arr, N) << endl;
    return 0;
}