gautam94's blog

How to recover actual sequence of moves from a DP solution?
By gautam94, 9 years ago, In English

I have written this code http://ideone.com/11kNYs for solving this problem http://codeforces.com/problemset/problem/219/C It asks for the minimum number of changes in a string such that no two adjacent characters are same and also only the first k characters can be used. The code is not yet complete as it's only calculating the minimum number of changes. The problem also requires the actual answer with minimum changes. So how to do this?

  • Vote: I like it
  • +6
  • Vote: I do not like it

»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

To recover the solution from the DP, whenever the answer for solve of (i,j) gets better (gets a smaller value than the present value) and say that solution is got from (k,l), then store (k,l) memo[i][j]. So we know that for each i,j how we got the best result. Now start iterating from the starting dp call. (n-1,'[') in your case and keep checking memo[i][j] until you get the base case. You can reconstruct the answer like that.

→ Reply