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:
- **way practice DP **
- 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 -https://www.youtube.com/watch?v=MwfvXDfaZeI -https://www.youtube.com/watch?v=MMY077l9awA -https://www.youtube.com/watch?v=oSQbwlepoCU -https://www.youtube.com/watch?v=IJDJ0kBx2LM
2.**Iterative** — n 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. -https://www.youtube.com/watch?v=oBt53YbR9Kk
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