学习要点
- 求最长递增字列
- 求最长递减子列
题目链接
合唱队_牛客题霸_牛客网
题目描述
解法：动归求最长递增子列
#include <iostream>
#include <vector>
using namespace std;int main() {int n;while (cin >> n) {// 输入的数组int tmp;vector<int> v;for (int i = 0; i < n; ++i) {cin >> tmp;v.push_back(tmp);}// 最长递增子序列 从左往右if (v.empty()) return 0;vector<int> dp1(n, 1);for (int i = 0; i < n; ++i) {for (int j = 0; j < i ; ++j) {if (v[i] > v[j]) {dp1[i] = max(dp1[i], dp1[j] + 1);}}}// 最长递减子序列 从右往左if (v.empty()) return 0;vector<int> dp2(n, 1);for(int i = n-1;i>=0;i--){for(int j = n-1;j>i;j--){if(v[i] > v[j]){dp2[i] = max(dp2[i],dp2[j]+1);}}}int result;for(int i =0;i<n;i++){result = max(result,dp1[i]+dp2[i]-1);}cout << n - result;}
}
// 64 位输出请用 printf("%lld")
)
)
