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
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
