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.
→ Pay attention
→ Top rated
| # | User | Rating |
|---|---|---|
| 1 | Benq | 3792 |
| 2 | VivaciousAubergine | 3647 |
| 3 | Kevin114514 | 3611 |
| 4 | jiangly | 3583 |
| 5 | strapple | 3515 |
| 6 | tourist | 3470 |
| 7 | dXqwq | 3436 |
| 8 | Radewoosh | 3415 |
| 9 | Otomachi_Una | 3413 |
| 10 | Um_nik | 3376 |
→ Top contributors
| # | User | Contrib. |
|---|---|---|
| 1 | Qingyu | 161 |
| 2 | adamant | 150 |
| 3 | Um_nik | 146 |
| 4 | Dominater069 | 144 |
| 5 | errorgorn | 141 |
| 6 | cry | 139 |
| 7 | Proof_by_QED | 136 |
| 8 | YuukiS | 135 |
| 9 | chromate00 | 134 |
| 9 | TheScrasse | 134 |
→ Find user
→ Recent actions
Codeforces (c) Copyright 2010-2026 Mike Mirzayanov
The only programming contests Web 2.0 platform
Server time: May/11/2026 04:55:38 (h1).
Desktop version, switch to mobile version.
Supported by
Erm. There is no "universal" technique. So which DP problem are you trying to address in particular?
LCS and LIS
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.
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.
Just store array of parent positions of a certain dp state and backtrack.
For this, is backtracking a must?
Yeah
Ok, thanks btw
How to do LCS reconstruction when space-optimized bottom-up DP(Space Complexity = O(n)) is used?
You may take a look at: this blog and comment
How to reconstruct solution for this problem: https://mirror.codeforces.com/contest/10/problem/D