Блог пользователя kobietvietcode

Автор kobietvietcode, история, 3 дня назад, По-английски

My cousin wants me to teach him more about Dynamic Programming to prepare for future CP competitions.

I have had lots of experience with competitive programming, but when asked to teach him, my mind goes blank and I can't come up with a propper roadmap to teach him. He also has the basics of competitive programming down, and he wants me to teach him some intermediate to advanced stuff.

He decided to focus on DP first, and asked me for some documents and problems to solve.

Can you please provide some useful DP techniques, optimizations and some example problems with varying difficulties?

I appreciate all of your help!

  • Проголосовать: нравится
  • +16
  • Проголосовать: не нравится

»
3 дня назад, # |
  Проголосовать: нравится +17 Проголосовать: не нравится

Go for the CSES problem set. It has a variety of questions covering a lot of common techniques.

»
3 дня назад, # |
Rev. 2   Проголосовать: нравится +9 Проголосовать: не нравится

some intermediate to advance topic i know :

1)digit dp

2)dp prefix sum optimization

3)bitmask dp

4)state rotation ideas

5)space optimization in dp

6)game theory (dp)

7) dp + binary search (used in many interval related problems)

»
2 дня назад, # |
Rev. 2   Проголосовать: нравится +3 Проголосовать: не нравится

Say him to Watch Shayan streams for DP , it is good beginner friendly to start

»
2 дня назад, # |
Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

If you want to experience all different types of DP at once, go to the AtCoder DP contest. It is a great collection of various types of DP problems. link : atcoder dp contest

In short, you may choose CSES dp section this is also good. Link : CSES DP

For full discovering dp problem, you can also follow Usaco Gold section of dp part.There are good tutorial and good problemset. Link : USACO GOLD Section DP

»
33 часа назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
  1. CP handbook (on cses site)
  2. cses problem set
  3. atcoder dp mashup contest This is what one of my senior suggested. Happy learning ;)