Can someone help in coming up with DP states for BABY | SPOJ

Link to problem(BABY).

So far what I tried ->

Two states say mask and p where set bits of mask denote the array indexes of baby’s array which we will be messing with in current iteration and p denotes that we need to find minimum moves to perfectly keep first p elements of baby array to actual valid array.

So we call solve(2^n - 1, k).

My Code.

I want to know if these DP states are fine or we need some other states, if it is can you define those.

Your states are correct but you did not search all cases and also indexing was wrong.

I have corrected your code Click Here

Here is my code also with AC


A suggestion: you don’t need the second dimension for DP since k is always equal to the number of set bits in mask.

1 Like

thanks. :slight_smile: