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 Chain 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
1. https://www.youtube.com/watch?v=fGznXJ-LTbI&list=PLb3g_Z8nEv1j_BC-fmZWHFe6jmU_zv-8s
2. https://www.youtube.com/watch?v=38yRq24Zpu4
10. Dp with bitmasks
1. https://www.youtube.com/watch?v=rlTkd4yOQpE 2. https://www.youtube.com/watch?v=8HOIj0RgcCU
In the end, I hope that you liked the blog and benefited from it, and I hope that there are no mistakes in it. I know that there are many things in the DP that I did not talk about, but this is what I reached until this moment. If I notice that the blog is liked by many of you, I will continue writing such as These blogs and on various topics such as Graph and Tree
I have just started competitive programming. I think this would help me to get started with Dynamic Programming. Is there a way to mark this blog for future reference?
In the bottom, beside the option to upvote & downvote there is an option to star(basically, it will add to your favourites for future reference). Hope it may help!
Thankyou shivanshshukla60