I've practiced for dp and i have found my weakness.its the dp state.somehow i never guessed it correctly.the states that i made was never relevant to the actual answer.its totally wrong.i have no clue whenever i try to make some dp states and just see if somethings correct.idk how poeple just solve dp like its 1+1.i do not know what do memoize.can someone help me?
→ Обратите внимание
→ Трансляции
→ Лидеры (рейтинг)
| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | tourist | 4009 |
| 2 | jiangly | 3823 |
| 3 | Benq | 3738 |
| 4 | Radewoosh | 3633 |
| 5 | jqdai0815 | 3620 |
| 6 | orzdevinwang | 3529 |
| 7 | ecnerwala | 3446 |
| 8 | Um_nik | 3396 |
| 9 | ksun48 | 3390 |
| 10 | gamegame | 3386 |
| Страны | Города | Организации | Всё → |
→ Лидеры (вклад)
| № | Пользователь | Вклад |
|---|---|---|
| 1 | cry | 164 |
| 1 | maomao90 | 164 |
| 3 | Um_nik | 163 |
| 4 | atcoder_official | 160 |
| 4 | adamant | 160 |
| 6 | -is-this-fft- | 158 |
| 7 | awoo | 157 |
| 8 | TheScrasse | 154 |
| 8 | Dominater069 | 154 |
| 8 | nor | 154 |
→ Найти пользователя
→ Прямой эфир
Codeforces (c) Copyright 2010-2024 Михаил Мирзаянов
Соревнования по программированию 2.0
Время на сервере: 14.11.2024 19:53:00 (k2).
Десктопная версия, переключиться на мобильную.
При поддержке
pls help
The more you practice the more intuitive it becomes, most of the time the dimensions depend on the parameter in your recursive approach.
oh wow practice! why i didnt think of that -_-
Is there any other secret I am unaware of?
then why not try it? This helped me a lot.
its because one should not guess dp states, instead one should derive it using recurrence relation.
How? or perhaps my elaboration is not that clear.lemme make an example.
take a classical LCS
we have 2 strings.with those strings we need to check the lcs.ofc bruteforce will come to mind first but it requires tons of loops and other things.WIth dp,we need to observe.but whenever i observe,its wrong.like for example,what do we need? the position of a specific characters? the number of occurence of a letter? the length? well idk unless soomeone tell me what matters.i would always guess.
lcs might be a bit obvious but think about more advance
You need "prefix of the array / string" as a state in $$$90\%$$$ of problems.
Think like this — Let currently you are at index i so what are the necessary information you should know from previous values to calculate the answer of current i, those informations will be your state of dp. You can always optimise your states from here.