Find minimum number of movement

Question

Given an array of 1 and 0. We need to move all 1's to 0 with minimum cost

1. We can move either left or right , multiple one's cannot be moved to same position.

2. Each movement cost is 1.

Ex:

    array = 0001101
    
    Here the optimal solution is 5 , x means it cannot be occupied 
    1. 3rd index to 2nd index -> cost = 1 , array = 00xx101  
    2. 4th index to 1st index -> cost = 3 , array = 0xxxx01
    3. 6th index to 5th index -> cost = 1 , array = 0xxxxxx

I tried it by bruteforce way of finding it's nearest 0 and moving it , but with no success. Need some expertise help here.

Edit:

I solved this problem using recusrion and memoization. Quite similar question with solution here - https://leetcode.com/problems/minimum-total-distance-traveled/solutions/2816471/recursion-memoization/

Answer 1

This can be solved with dynamic programming.

Let the state space be the set of strings with n characters from the alphabet {0, 1, x}.

The transitions are defined by changing ones and zeros to x after moving a 1 to the closest 0 to the left or to the right.

The base cases are the strings full of 0 and x characters (for which you return zero) or a string from which you cannot move (for which you return -1).

For example, if the initial state is 0001101, the possible transitions are 00xx101, 0001xx1 and 00011xx.

The solution for a state is the minimum of the solutions for all the possible transitions (plus the cost of doing the transition) only for the solutions that are not -1. If all the transition solutions are -1, the solution for the state is also -1.

To store solutions for states, you can use a hash map.