I feel like I'm extremely weak on DP problems. Can somebody suggest a way to practice DP?
→ Обратите внимание
До соревнования
Rayan Programming Contest 2024 - Selection (Codeforces Round 989, Div. 1 + Div. 2)
4 дня
Зарегистрироваться »
Rayan Programming Contest 2024 - Selection (Codeforces Round 989, Div. 1 + Div. 2)
4 дня
Зарегистрироваться »
*есть доп. регистрация
→ Лидеры (рейтинг)
| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | tourist | 3993 |
| 2 | jiangly | 3743 |
| 3 | orzdevinwang | 3707 |
| 4 | Radewoosh | 3627 |
| 5 | jqdai0815 | 3620 |
| 6 | Benq | 3564 |
| 7 | Kevin114514 | 3443 |
| 8 | ksun48 | 3434 |
| 9 | Rewinding | 3397 |
| 10 | Um_nik | 3396 |
| Страны | Города | Организации | Всё → |
→ Лидеры (вклад)
| № | Пользователь | Вклад |
|---|---|---|
| 1 | cry | 167 |
| 2 | Um_nik | 163 |
| 3 | maomao90 | 162 |
| 3 | atcoder_official | 162 |
| 5 | adamant | 159 |
| 6 | -is-this-fft- | 158 |
| 7 | awoo | 155 |
| 8 | TheScrasse | 154 |
| 9 | Dominater069 | 153 |
| 10 | nor | 152 |
→ Найти пользователя
→ Прямой эфир
Codeforces (c) Copyright 2010-2024 Михаил Мирзаянов
Соревнования по программированию 2.0
Время на сервере: 26.11.2024 23:27:46 (i2).
Десктопная версия, переключиться на мобильную.
При поддержке
I suggest reading these https://codeforces.me/blog/entry/67679 https://codeforces.me/blog/entry/80064 https://codeforces.me/blog/entry/70018
Try to solve DP problems using tabulation method and first of all try to understand 0-1 knapsack. Tabulation method will provide you a more clear understanding how dp actually works
I know how DP works, but I just can't figure out how to use DP in problems.
For solving DP problems try to form a state for the problems and try to see how to change from one state to another. For forming a state try to minimise the problem, like for forming Fibonacci series try to see how fib(4) could be formed from fib(3) and for changing the state see what changes are being done for getting fib(4) from fib(3)
Well, to get into DP, I would suggest you to do some beginner DP problem set, such as CSES, Atcoder (this one does contain some relatively hard stuff so I would suggest complete like 75% of them). Then, you would pull off the pro-gamer move in your training, which is not doing DP problem set, and just solve everything thrown at you. As counter-intuitive as it may sounds, not specifically doing DP problem will benefits you greatly, as it will train your ability to notice DP problems, as well as changing your mindset to use DP as a tool, not as the entire solution. I've met quite a few problems where DP is the easiest part lol.
Thanks a lot! By the way, could you give some tips on how to reach candidate master?
you should get proficient at basic techniques, such at binary searching, two pointers, dynamic programming, hash and basic graph knowledge. You should also get to a certain point of math maturity. I know several people who are not that good at math, therefore it took them an excessively long time to reach Candidate Master. Some have been at Expert for like a whole 3 years.
From my experience, the best way is to just practice. It helps improve your skill and your experience to deal with problems in the future. About the problem source, I suggest the CSES problem set, it contains some nice DP problem that you can do to practice. Hope it'll help!