将三个组排序

给定数组只含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;
    }
};