Need help for a DP problem

Need help for a DP problem

By diavolobia, 21 hour(s) ago,

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≤5000), the block at the ith position has the color of ci (1≤ci≤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 1

Sample 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:

dp[l][r][k]=minr−1i=l⎛⎝⎜⎜⎜⎜dp[l][i][0]+dp[i+1][r][0]+(color[l][i][0]≠color[i+1][j][0]),dp[l][i][1]+dp[i+1][r][0]+(color[l][i][1]≠color[i+1][j][0]),dp[l][i][0]+dp[i+1][r][1]+(color[l][i][0]≠color[i+1][j][1]),dp[l][i][1]+dp[i+1][r][1]+(color[l][i][1]≠color[i+1][j][1])⎞⎠⎟⎟⎟⎟

where color[l][r][k] is the color of the segment [l,r] after being painted optimally. This formula has N2 states and each transition costs O(N), which makes the time complexity of this approach O(N3) — 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?