Ok, I couldn't try working it out by hand - didn't get time. I'll try that soon and get back. However, I came across another problem and this was in a contest. This clearly is a DP problem and I came up with a solution too (and only then I realised I understood DP!). I would however prefer it getting 'approved' by you! I think it is right, though can't say it with surety.

Here's the problem:

You are given a string of length 7 consisting of characters 1 to 7

Following operations are legal:

1. You can chuck off the first char temporarily and shift the adjacent 3 towards left.

2. You can chuck off the last char temporarily and shift the adjacent 3 towards right.

3. You can chuck off the middle char temporarily and shift the adjacent 3 (on the left) towards right.

4. You can chuck off the middle char temporarily and shift the adjacent 3 (on the right) towards left.

e.g. if you are given "3452671",

applying 1: you get "4523671"

applying 2: you get "3456712"

applying 3: you get "2345671"

applying 4: you get "3456712"

The question is to find the minimum number of steps required to convert a given string to "1234567".

My method:

I just somehow conjectured (and not proved) that whenever we apply a transformation, we must get 'towards' the string "1234567" and our 'closeness' can be measured in terms of 'breaks' we have in the string.

e.g. "2345617" has two 'breaks'. That is, 23456 is one unit, 1 is one, and 7 is one. So two breaks.

Let F(s, Ti) be a function that tells us how many breaks are there in the string s, after applying the transformation Ti to it.

Let N(s) be the function that tells how many steps it takes to convert string s to "1234567".

N(s) is defined as:

N(s) = 0 if s == "1234567"

N(s): 1 + min{ N( Ti(s) ) }

where Ti(s) returns the transformed string.

(ignore the F(s, Ti) part. I was going to tell something about it and suddenly changed the idea)

Is this correct????

Another Parth? Wow.