TwoDot's blog

I can't understand dp
By TwoDot, history, 18 months ago, In English

Do anyone know how can i learn how to use dp algorithm? like, i cant use anything that i read from books and i need to learn it.

  • Vote: I like it
  • +7
  • Vote: I do not like it

Comments Comments (12)
| Write comment?
»
18 months ago, # |
  Vote: I like it +4 Vote: I do not like it

Start with the fundamental problems. CSES Problem Set is a great resource. Spend some time on each problem you solve on your own or by seeing the solution. Understand the intuition of how the states are linked to each other, how the base cases, and finally the final subproblem is formulated. Understand the Transitions very thoroughly and analyze why such Transitions. After you do 50-60% of the Problem set you are good to go. Now only practicing good problems would take you further.

→ Reply
»
18 months ago, # |
  Vote: I like it +6 Vote: I do not like it

  1. Learn Recursion (You are given : [1,2,3,4,5,6]. Now you are able to write a code that will generate all possible combinations for ex. [2,3,4,1,5,6], [3,2,5,6,1,4]... total of 6! combinations using recursion and you understand how the code works).

  2. Learn backtracking (Solve 8-queens problem and understand how the recursion works)

  3. Read these 2 tutorials : Tutorial-1 Tutorial-2

→ Reply
»
18 months ago, # |
  Vote: I like it +3 Vote: I do not like it

You need to do some meditation first to develop enough concentration. With love.

→ Reply
»
18 months ago, # |
  Vote: I like it +1 Vote: I do not like it

hard luck bozo

→ Reply
»
18 months ago, # |
  Vote: I like it 0 Vote: I do not like it

The Atcoder educational dp contest might also help.

→ Reply
»
18 months ago, # |
← Rev. 3   Vote: I like it +11 Vote: I do not like it

The one thing that helped me immensely in understanding DP are Errichto youtube videos on dynamic programming where he goes over some basic and very common DP problems. Good luck!

→ Reply
»
18 months ago, # |
  Vote: I like it 0 Vote: I do not like it

The answers mostly discuss practice, and are quite comprehensive in their coverage of resources. I would like to add though, one might need to go over blogs/videos multiple times in order to understand the same. Don't be disheartened by that. Also, you can refer to this blog for the basic idea of DP.

→ Reply
»
18 months ago, # |
  Vote: I like it +6 Vote: I do not like it

https://www.youtube.com/playlist?list=PLgUwDviBIf0qUlt5H_kiKYaNSqJ81PMMY

you can see this, it helped me a lot .

→ Reply
»
18 months ago, # |
  Vote: I like it +12 Vote: I do not like it

i personally wouldn't advise learning dp at rating 588. I recommend practicing problems at the moment and then you should start of with some algorithms such as binary search

→ Reply
»
4 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Start with problem in atcoder dp contest, in this contest appear all basic techniques. Good luck for problem solving!

→ Reply
  • »
    »
    4 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Bruh

    → Reply
»
3 days ago, # |
  Vote: I like it 0 Vote: I do not like it

buddy dp is a optimization technique. not the idea to solve a question. the main idea requried to solve the question is always something else, you just use dp to optimize it :) change pov

→ Reply