Dynamic Programming

Revision en50, by OmarNabill, 2022-04-25 23:07:24

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

2. 1d Array

3. 2d array

4. Strings

5. Counting

6. Breaking And partition

7. Mathematical problem

  • Matrix Change Multiplication

  • Best Time to Buy And sell stock

8. Stundard problem

9. Dp with tree https://www.youtube.com/watch?v=fGznXJ-LTbI&list=PLb3g_Z8nEv1j_BC-fmZWHFe6jmU_zv-8s
https://www.youtube.com/watch?v=38yRq24Zpu4

10. Dp with bitmasks https://www.youtube.com/watch?v=rlTkd4yOQpE https://www.youtube.com/watch?v=8HOIj0RgcCU

History

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