I'm solving my school's DP problem set. Since it's not in English so I'll try my best to translate the problem.
There is a wall of N blocks ($$$N \leq 5000$$$), the block at the $$$i_{th}$$$ position has the color of $$$c_i$$$ ($$$1 \leq c_i \leq 5000$$$ for all $$$i$$$).
A painter needs to paint the so all blocks of the wall have the same color. It can be whichever color, it just needs to be the same for all blocks. One at a time, he does the following operation: Choose a segment of the wall, then use a color to paint all the blocks in that segment to the same color.
As a professional painter he knows that if he paints the same color to 2 blocks with different colors, the color will end up distorted, so he only paints a segment of which all the blocks have the same color. Because he is lazy, tell him the minimum operations he needs to paint the wall.
Sample input:
4
5 2 2 1Sample output: 2
Explanation:
First he can paint the segment [2, 3] to color 5. The wall becomes 5 5 5 1.
Then he can paint the segment [1, 3] to color 1. The wall becomes 1 1 1 1.
I've came up with a DP solution that looks like this: Let $$$dp[l][r][k]$$$ be the minimum operations needed to paint the segment $$$[l, r]$$$ to the same color, with $$$k$$$ is a boolean to identify whether the segment should be painted to the left part's color or the right one.
My transition formula is:
where $$$color[l][r][k]$$$ is the color of the segment $$$[l, r]$$$ after being painted optimally. This formula has $$$N^2$$$ states and each transition costs $$$O(N)$$$, which makes the time complexity of this approach $$$O(N^3)$$$ — too slow for the problem's constraints.
Is there anything I can do to speed up the transition part? Or do I have to tackle this problem from a different approach?
Hello, i think I got a solution (this might be wrong).
Firstly, you can notice that if you have a segment of the same color (in the given array) you can treat it as a single number. Exemple : (5 5 6 7 2 2 3 3 3) this is the same as (5, 6, 7, 2, 3). This is because you can change the whole segment (with the same color in just 1 operation).
The state is dp[i][j] which means the minimum number of operations to turn the first i blocks into the same color.
Now, the transitions : You have 2 choices : 1) You dont change the color of the ith block : dp[i][j] = dp[i — 1][j] Here j needs to be the color of the ith block.
2) You change the color of the ith block : dp[i][j] = dp[i — 1][j] + 1; You need to do +1 because you change the color of the ith block
If you don't understand something feel free to comment. If you want the code i can send it with discord.
I think that your solution is correct.
The only point not mentioned in your comment is that the second index $$$j$$$ of the state $$$dp[i][j]$$$ is the final color of the first $$$i$$$ segments of consecutive blocks with the same initial color.
The initial state should be $$$dp[0][j] = 0$$$ for $$$1 \leq j \leq 5000$$$.
The required answer should be computed as follows after iterating on $$$i$$$ from $$$1$$$ to $$$k$$$ as follows.
$$$\min\limits_{j=1}^{j=5000} dp[k][j]$$$
where $$$k$$$ is the number of segments of consecutive blocks with the same color, and $$$1 \leq k \leq N$$$.
The state-update equation can be expressed as follows.
$$$dp[i][j] = dp[i-1][j]+(s[i]\neq j)$$$
where $$$s[i]$$$ is the initial color of the $$$i$$$-th segment.
Does this not disregard cases where it is optimal to change an index twice?
for example 01210 can be completed with 01210 01110 00000
this feels like range dp?
Yes, it does. Painting the block with color 2 twice brings the minimum number of operations down to 2, while the minimum number of operations using left-to-right scanning with painting at most once is 3. Thanks for this counterexample.
My friends also came up with similar DP solutions but received wrong answer. Turns out Whimpers was right, their solutions didn't consider the case where it is optimal to change an index twice.
Another problem with the solution is that it forces the whole segment from $$$[1, i - 1]$$$ to have the same color before changing, which isn't always the optimal answer (the optimal way might be painting the middle part first then change the outside later, like Whimpers' example). That's why my DP solution takes both $$$l$$$ and $$$r$$$ as parameters.