---
# System prepended metadata

title: 2826. Sorting Three Groups
tags: [Leetcode, Dynamic Programming, Medium]

---

Link: https://leetcode.com/problems/sorting-three-groups/description/
## 思路
核心就是用最少的operation构建一个由1, 2, 3组成的non-decreasing array
```dp[i]```表示构建一个最大值是```i```的array需要的最少的operation
Since we don't need to apply any extra operation to ```dp[num]``` if current number equals to ```num```, we first add all dp elements by 1, and then delete 1 from ```dp[num]```
```dp[2]``` could include all the possibility in ```dp[1]``` and same to ```dp[3]```

## Code
```python=
class Solution:
    def minimumOperations(self, nums: List[int]) -> int:
        # non-decreasing array consist by only 1, 2, 3
        n = len(nums)
        dp = [0]*4
        for num in nums:
            for i in range(1, 4):
                dp[i] += 1
            dp[num] -= 1
            dp[2] = min(dp[1], dp[2])
            dp[3] = min(dp[2], dp[3])
        return dp[3]
```