Is there any way to space optimize a recursive DP for example say the 0-1 knapsack problem where we can do it iteratively using a 2xN dp array iteratively. Recently I came across this probelem and this problem where I was forced to use an iterative DP. Is there any way to solve these problems recursively?
→ Обратите внимание
→ Трансляции
→ Лидеры (рейтинг)
| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | tourist | 3985 |
| 2 | jiangly | 3814 |
| 3 | jqdai0815 | 3682 |
| 4 | Benq | 3529 |
| 5 | orzdevinwang | 3526 |
| 6 | ksun48 | 3517 |
| 7 | Radewoosh | 3410 |
| 8 | hos.lyric | 3399 |
| 9 | ecnerwala | 3392 |
| 9 | Um_nik | 3392 |
| Страны | Города | Организации | Всё → |
→ Лидеры (вклад)
| № | Пользователь | Вклад |
|---|---|---|
| 1 | cry | 169 |
| 2 | maomao90 | 162 |
| 2 | Um_nik | 162 |
| 4 | atcoder_official | 161 |
| 5 | djm03178 | 158 |
| 6 | -is-this-fft- | 157 |
| 7 | adamant | 155 |
| 8 | Dominater069 | 154 |
| 8 | awoo | 154 |
| 10 | luogu_official | 150 |
→ Найти пользователя
→ Прямой эфир
Codeforces (c) Copyright 2010-2024 Михаил Мирзаянов
Соревнования по программированию 2.0
Время на сервере: 23.12.2024 15:05:10 (h1).
Десктопная версия, переключиться на мобильную.
При поддержке
Why don't you like the iterative approach? It will already have O(n) memory. You won't have any recursion that uses less than O(n) memory here.
I think it's not about liking or disliking . I just find that iterative dp is a bit hard to implement than the recursive dp . So noobs like me generally prefer recursive dp .
Do you prefer recursive dp because you are noobs or are you noobs because you prefer recursive dp?
both.
Ashishgup prefer recursive dp most of the time and he is definitely not a noob.
Its just because recursive is slower than iterative and requires more memory in some cases where you are initializing any container. If you see these problems even Ashishgup used recursive first and then commented that part out 36262262.
That's why, I said
most of the timeI like recursive dp!
Recursive dp is just more intuitive to me, and it's the first solution that comes to my mind. Converting it to iterative takes a bit of time and is confusing for me if it contains more than two states.
Most of the time it's not possible to do such space optimization(unless you are removing a state from recursive dp approach which is dependent on other and can be derived from other states) in recursive dp.
Sometimes, it can be helpful in reducing time complexity in some cases where all the states need not to be calculated(because iterative dp calculates all earlier states and then only moves forward). An example of such a problem is this.