给定数组只含1、2、3三种数
每次操作可以将一个数进行修改
将数组修改成非递减顺序的最少次数
1. 暴力（笨比做法）
枚举三种类型数分割的界限
class Solution {
public:
int minimumOperations(vector<int>& nums) {
int res = INT_MAX;
int n = nums.size();
vector<vector<int>> presum(n+1,vector<int>(4));
for(int i=0;i<n;i++){
presum[i+1][1] = presum[i][1]; //继承
presum[i+1][2] = presum[i][2]; //继承
presum[i+1][3] = presum[i][3]; //继承
presum[i+1][nums[i]]++;//增加
}
for(int i=0;i<=n;i++){//枚举2的起始位置.一共n+1个候选位置
for(int j=i;j<=n;j++){//枚举3的起始位置，可以将2覆盖掉
//计算1的在位个数
int cur = presum[i][1];
//计算2的在位个数
cur = cur + presum[j][2] - presum[i][2];
//计算3的在位个数
cur = cur + presum[n][3] - presum[j][3];
res = min(res,n-cur);
}
}
return res;
}
};
2. 动态规划
将问题转化为最长递增子序列
class Solution {
public:
int minimumOperations(vector<int>& nums) {
int res = 0;
int n = nums.size();
vector<int> dp(4);//以三种数为结尾的最长递增子序列长度
for(int i=0;i<n;i++)
for(int j=nums[i];j>=1;j--){//从三个状态进行转移
dp[nums[i]] = max(dp[nums[i]],dp[j]+1);
res = max(res,dp[nums[i]]);
}
return n - res;
}
};