Dynamic Programming

Правка en40, от OmarNabill, 2022-04-25 22:41:25

After searching a lot about how to start studying Dynamic Programming and what are the important topics that I should study and how to practice on them, I found that:

1. Way practice DP

1. Recursion

- A procedure that contains a procedure call to itself or a procedure call to a second procedure which eventually causes the first procedure to be called is known as a recursive procedure.

2. Iterative

  • the other hand, uses looping in order to execute a set of statements multiple times. A given problem can be solved both by recursion as well as iteration, however, they have certain important differences as well.

3. Memoization

  • Memoization is a way to potentially make functions that use recursion run faste a recursive function might end up performing the same calculation with the same input multiple times. This means it could end up taking longer than the iterative alternative.A memoization function allows us to store input alongside the result of the calculation. Therefore, rather than having to do the same work again using the same input, it can simply return the value stored in the cache.

2. resources to practice DP

  1. https://atcoder.jp/contests/dp/tasks

  2. https://vjudge.net/group/icpcassiutjunuiorsphase2

3. Content Flow

1. Basic problems

  • fibonacci problem

  • staircase problem

2. 1d Array

  • longest increasing subsequence

  • minimum jumps to reach end

  • Loot Houses

3. 2d array

  • Min Cost Path

  • 0-1 Knapsack

4. Strings

  • longest Common subsequence

  • Edit Distance

  • find if string is interleaved of two strings

5. Counting

  • Coin Change

  • count balanced binary trees of height of n

6. Breaking And partition

  • Palindrom Partitioning

  • Partition Equal subset sum

7. Mathematical problem

  • Matrix Change Multiplication

  • Best Time to Buy And sell stock

8. Stundard problem

  • Rod Cutting

  • Counting Palindromic subsequence

  • longest Palindromic substring

  • Optimal BST

  • Distinct subsequence

9. Dp with tree

10. Dp with bitmasks

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en66 Английский OmarNabill 2022-04-26 01:17:34 3 Tiny change: 'Matrix Change Multiplic' -> 'Matrix Chain Multiplic'
en65 Английский OmarNabill 2022-04-25 23:32:06 0 (published)
en64 Английский OmarNabill 2022-04-25 23:30:55 14 Tiny change: 'ursion**\n- a proced' -> 'ursion**\n - a proced'
en63 Английский OmarNabill 2022-04-25 23:29:38 1 Tiny change: 'h and Tree **' -> 'h and Tree**'
en62 Английский OmarNabill 2022-04-25 23:28:48 7
en61 Английский OmarNabill 2022-04-25 23:28:29 1
en60 Английский OmarNabill 2022-04-25 23:28:13 11
en59 Английский OmarNabill 2022-04-25 23:27:55 1 Tiny change: 'n\n\n\n\n #### In t' -> 'n\n\n\n\n #### In t'
en58 Английский OmarNabill 2022-04-25 23:27:21 8 Tiny change: 'Ij0RgcCU\n #### In' -> 'Ij0RgcCU\n\n\n\n\n #### In'
en57 Английский OmarNabill 2022-04-25 23:26:47 380
en56 Английский OmarNabill 2022-04-25 23:21:43 2 Tiny change: 'd4yOQpE \n 2. ' -> 'd4yOQpE \n\n 2. '
en55 Английский OmarNabill 2022-04-25 23:21:04 38
en54 Английский OmarNabill 2022-04-25 23:19:45 2 Tiny change: 'd4yOQpE \n &md' -> 'd4yOQpE \n\n &md'
en53 Английский OmarNabill 2022-04-25 23:19:21 4
en52 Английский OmarNabill 2022-04-25 23:14:55 5530
en51 Английский OmarNabill 2022-04-25 23:09:17 30
en50 Английский OmarNabill 2022-04-25 23:07:24 735
en49 Английский OmarNabill 2022-04-25 22:58:09 606
en48 Английский OmarNabill 2022-04-25 22:53:17 363
en47 Английский OmarNabill 2022-04-25 22:48:19 6 Tiny change: '6bIZ5KY 2.https://ww' -> '6bIZ5KY \n 2. https://ww'
en46 Английский OmarNabill 2022-04-25 22:47:56 106
en45 Английский OmarNabill 2022-04-25 22:46:32 53
en44 Английский OmarNabill 2022-04-25 22:42:30 6 Tiny change: 'ursion**\n\n a procedu' -> 'ursion**\n- a procedu'
en43 Английский OmarNabill 2022-04-25 22:42:13 2 Tiny change: '**\n\n - a procedu' -> '**\n\n a procedu'
en42 Английский OmarNabill 2022-04-25 22:41:56 12 Tiny change: 'ursion**\n — A procedure' -> 'ursion**\n\n - a procedure'
en41 Английский OmarNabill 2022-04-25 22:41:40 10 Tiny change: 'ursion**\n\n - A ' -> 'ursion**\n - A '
en40 Английский OmarNabill 2022-04-25 22:41:25 1 Tiny change: '\n\n - A procedu' -> '\n\n - A procedu'
en39 Английский OmarNabill 2022-04-25 22:41:10 1 Tiny change: 'n\n - A proced' -> 'n\n - A proced'
en38 Английский OmarNabill 2022-04-25 22:41:01 21
en37 Английский OmarNabill 2022-04-25 22:40:31 15
en36 Английский OmarNabill 2022-04-25 22:39:49 18 Tiny change: 'n\n **2. Basic problems**\n\n - ' -> 'n\n **2. 1d Array**\n\n - '
en35 Английский OmarNabill 2022-04-25 22:39:25 17 Tiny change: '\n\n\n\n **2. Array **\n\n - ' -> '\n\n\n\n **2. Basic problems**\n\n - '
en34 Английский OmarNabill 2022-04-25 22:39:05 3 Tiny change: '\n **2. 1d Array **\' -> '\n **2. Array **\'
en33 Английский OmarNabill 2022-04-25 22:38:50 1 Tiny change: '\n\n\n\n **2. 1d ' -> '\n\n\n\n **2. 1d '
en32 Английский OmarNabill 2022-04-25 22:38:32 61
en31 Английский OmarNabill 2022-04-25 22:37:11 2
en30 Английский OmarNabill 2022-04-25 22:36:36 23
en29 Английский OmarNabill 2022-04-25 22:35:28 28
en28 Английский OmarNabill 2022-04-25 22:34:58 32
en27 Английский OmarNabill 2022-04-25 22:34:24 3
en26 Английский OmarNabill 2022-04-25 22:33:19 8
en25 Английский OmarNabill 2022-04-25 22:33:08 1 Tiny change: '### After ' -> '#### After '
en24 Английский OmarNabill 2022-04-25 22:33:00 4 Tiny change: 'After sear' -> '### After sear'
en23 Английский OmarNabill 2022-04-25 22:32:36 29
en22 Английский OmarNabill 2022-04-25 22:31:28 25
en21 Английский OmarNabill 2022-04-25 22:30:48 27
en20 Английский OmarNabill 2022-04-25 22:30:32 38 Tiny change: ' that:\n\n\n1. **Way' -> ' that:\n\nWay practice DP...\n==================\n1. **Way'
en19 Английский OmarNabill 2022-04-25 22:29:54 1 Tiny change: '*\n\n\n 1. **Re' -> '*\n\n\n 1. **Re'
en18 Английский OmarNabill 2022-04-25 22:29:46 2 Tiny change: '**\n\n\n 1. **Rec' -> '**\n\n\n 1. **Rec'
en17 Английский OmarNabill 2022-04-25 22:29:24 15
en16 Английский OmarNabill 2022-04-25 22:28:55 1 Tiny change: 't:\n\n\n1.**Way prac' -> 't:\n\n\n1. **Way prac'
en15 Английский OmarNabill 2022-04-25 19:56:07 51
en14 Английский OmarNabill 2022-04-25 19:54:16 1 Tiny change: 'e**\n\n - the o' -> 'e**\n\n - the o'
en13 Английский OmarNabill 2022-04-25 19:53:49 1 Tiny change: '*\n\n -n the other' -> '*\n\n - the other'
en12 Английский OmarNabill 2022-04-25 19:53:26 22
en11 Английский OmarNabill 2022-04-25 19:52:34 1
en10 Английский OmarNabill 2022-04-25 19:51:57 4
en9 Английский OmarNabill 2022-04-25 19:51:40 66
en8 Английский OmarNabill 2022-04-25 19:50:29 8
en7 Английский OmarNabill 2022-04-25 19:50:05 6
en6 Английский OmarNabill 2022-04-25 19:49:55 4 Tiny change: 'omputation \n -http' -> 'omputation.\n\n -http'
en5 Английский OmarNabill 2022-04-25 19:49:15 13
en4 Английский OmarNabill 2022-04-25 19:48:27 2
en3 Английский OmarNabill 2022-04-25 19:48:06 2 Tiny change: 'n\n\n1. **way practic' -> 'n\n\n1. **Way practic'
en2 Английский OmarNabill 2022-04-25 19:47:48 1 Tiny change: 'ctice DP**\n 1. h' -> 'ctice DP***\n 1. h'
en1 Английский OmarNabill 2022-04-25 19:46:42 2677 Initial revision (saved to drafts)