JacobianDet's blog

DP SOLUTION RECONSTRUCTION
By JacobianDet, history, 5 years ago, In English

How to reconstruct all possible solutions of a particular DP problem? I'm not able to get a generalized technique for this and only results for LCS are shown regarding an example of this topic.

Tags dp
  • Vote: I like it
  • 0
  • Vote: I do not like it

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

Erm. There is no "universal" technique. So which DP problem are you trying to address in particular?

→ Reply
»
5 years ago, # |
  Vote: I like it +3 Vote: I do not like it

When you see a DP problem, you shouldn't try to frame your solution around some general approach. Each problem is unique (unless its a dumb problem) so you should make some observations beforehand which may lead to a recurrence.

→ Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    No, I'm not asking about DP recurrences, I'm asking about some ideas regarding the reconstruction of all possible solutions after running the DP recurrence. Like there is the parent pointer technique to get one of the possible solutions of the problem.

    → Reply
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

How to do LCS reconstruction when space-optimized bottom-up DP(Space Complexity = O(n)) is used?

→ Reply
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

How to reconstruct solution for this problem: https://codeforces.com/contest/10/problem/D

→ Reply