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.
→ Обратите внимание
→ Трансляции
→ Лидеры (рейтинг)
| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | tourist | 3985 |
| 2 | orzdevinwang | 3844 |
| 3 | jqdai0815 | 3682 |
| 4 | jiangly | 3618 |
| 5 | Benq | 3529 |
| 6 | ksun48 | 3489 |
| 7 | Radewoosh | 3483 |
| 8 | Kevin114514 | 3443 |
| 9 | ecnerwala | 3392 |
| 9 | Um_nik | 3392 |
| Страны | Города | Организации | Всё → |
→ Лидеры (вклад)
| № | Пользователь | Вклад |
|---|---|---|
| 1 | cry | 167 |
| 2 | Um_nik | 163 |
| 3 | atcoder_official | 162 |
| 3 | maomao90 | 162 |
| 5 | adamant | 159 |
| 6 | -is-this-fft- | 158 |
| 7 | awoo | 155 |
| 8 | TheScrasse | 154 |
| 9 | Dominater069 | 153 |
| 10 | djm03178 | 152 |
→ Найти пользователя
→ Прямой эфир
Codeforces (c) Copyright 2010-2024 Михаил Мирзаянов
Соревнования по программированию 2.0
Время на сервере: 02.12.2024 02:13:33 (i1).
Десктопная версия, переключиться на мобильную.
При поддержке
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://codeforces.me/contest/10/problem/D