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

[adecemberguy]

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.

[anushi]

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

[meooow]

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

[adecemberguy]

thanks.