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.
There are two important conditions that must be satisfied by any recursive procedure Each time a procedure calls itself it must be nearer in some sense to a solution There must be a decision criterion for stopping the process or computation.
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
3. Content Flow
1. Basic problems
fibonacci problem https://www.youtube.com/watch?v=YkBch12jNE0
staircase problem https://www.youtube.com/watch?v=0zvG6bIZ5KY https://www.youtube.com/watch?v=jAGyNmrJuPE
2. 1d Array
longest increasing subsequence O(n^2)https://www.youtube.com/watch?v=okgM58Tv9jQ&t=496s
O(nlogn) https://www.youtube.com/watch?v=i4NBDE8ZEV8minimum jumps to reach end https://www.youtube.com/watch?v=0cjO51vAY44&t=31s
Loot Houses https://www.youtube.com/watch?v=xlvhyfcoQa4
3. 2d array
Min Cost Path https://www.youtube.com/watch?v=t1shZ8_s6jc
0-1 Knapsack https://www.youtube.com/watch?v=PPcpC5QbMx0&t=645s https://www.youtube.com/watch?v=xOlhR_2QCXY
4. Strings
longest Common subsequence https://www.youtube.com/watch?v=Esx-TxF5PSo
Edit Distance https://www.youtube.com/watch?v=AuYujVj646Q&t=284s
find if string is interleaved of two strings https://www.youtube.com/watch?v=jaQF6FSWYdE
5. Counting
Coin Change https://www.youtube.com/watch?v=jaNZ83Q3QGc https://www.youtube.com/watch?v=ZI17bgz07EE&t=1s https://www.youtube.com/watch?v=GBBRjI_1LRI
count balanced binary trees of height of n https://www.youtube.com/watch?v=pyO2FJE7G9o
https://www.youtube.com/watch?v=bh4eb_6SwRA
6. Breaking And partition
Palindrom Partitioning https://www.youtube.com/watch?v=lDYIvtBVmgo https://www.youtube.com/watch?v=szKVpQtBHh8 https://www.youtube.com/watch?v=WPr1jDh3bUQ
Partition Equal subset sum https://www.youtube.com/watch?v=obhWqDfzwQQ https://www.youtube.com/watch?v=7win3dcgo3k
7. Mathematical problem
Matrix Change Multiplication
Best Time to Buy And sell stock
8. Stundard problem
Rod Cutting https://www.youtube.com/watch?v=ElFrskby_7M https://www.youtube.com/watch?v=mO8XpGoJwuo
https://www.youtube.com/watch?v=nYJDp0Hj7M4Counting Palindromic subsequence https://www.youtube.com/watch?v=vlbA8oUxSV0
https://www.youtube.com/watch?v=YHSjvswCXC8longest Palindromic substring https://www.youtube.com/watch?v=UflHuQj6MVA https://www.youtube.com/watch?v=Fi5INvcmDos
Optimal BST https://www.youtube.com/watch?v=HnslzEs8dbY https://www.youtube.com/watch?v=vLS-zRCHo-Y
Distinct subsequence https://www.youtube.com/watch?v=nVG7eTiD2bY https://www.youtube.com/watch?v=-RDzMJ33nx8
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
