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

Автор AzaLE, история, 20 месяцев назад, По-английски

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.

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

»
20 месяцев назад, # |
  Проголосовать: нравится +4 Проголосовать: не нравится

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.

»
20 месяцев назад, # |
  Проголосовать: нравится +6 Проголосовать: не нравится
  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

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

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

»
20 месяцев назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

hard luck bozo

»
20 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

The Atcoder educational dp contest might also help.

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

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!

»
20 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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.

»
20 месяцев назад, # |
  Проголосовать: нравится +6 Проголосовать: не нравится
»
20 месяцев назад, # |
  Проголосовать: нравится +12 Проголосовать: не нравится

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

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

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

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

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