You are given an integer array nums. Each element in nums is 1, 2 or 3. In each operation, you can remove an element from nums. Return the minimum number of operations to make numsnon-decreasing.
Example 1:
Input:nums = [2,1,3,2,1]
Output:3
Explanation:
One of the optimal solutions is to remove nums[0], nums[2] and nums[3].
Example 2:
Input:nums = [1,3,2,1,3,3]
Output:2
Explanation:
One of the optimal solutions is to remove nums[1] and nums[2].
Example 3:
Input:nums = [2,2,2,2,3,3]
Output:0
Explanation:
nums is already non-decreasing.
Constraints:
1 <= nums.length <= 100
1 <= nums[i] <= 3
Follow-up: Can you come up with an algorithm that runs in O(n) time complexity?
Solutions
Solution 1: Dynamic Programming
We define $f[i][j]$ as the minimum number of operations to turn the first $i$ numbers into a beautiful array, and the $i$th number is changed to $j+1$. The answer is $\min(f[n][0], f[n][1], f[n][2])$.
We can enumerate all cases where the $i$th number is changed to $j+1$, and then take the minimum value. Here, we can use a rolling array to optimize the space complexity.
The time complexity is $O(n)$, where $n$ is the length of the array. The space complexity is $O(1)$.