Subodh — Toph

Problem link : https://toph.co/p/subodh

Here, We can start coloring from any side of the wall. Lets start color from 1st wall. Now, it is greedily best option to color all the wall with color[1]. Now, I have to color wall from 2 to Nth. Here, there could be walls i in (2 to N) for which color[i] = color[1]. So, I have to choose a position i for which color[i] = color[1] , then this problem will be divided into two subproblem ( 2 to i — 1 and i to N) and number of moves is also minimum after that. Now, this approach is optimal because we don’t have to recolor ith wall.

Now, I have to solve this 2 new subproblem same way as above. So, I can implement it using DP. DP[ left ] [ right ] represents minimum number of moves needed to color the range from left to right.

for(i = position of color same as left) {
    int val = (1 + dp[left + 1][i - 1]) + dp[i][right]; // add 1 because color full segment with color[left + 1]
    ans = min(ans, val);
}

Code : https://ideone.com/X01edF