Dynamic Programming Learning Resources

As a learner in Competitive Programming (CP), I've found certain resources invaluable for grasping Dynamic Programming (DP) concepts, despite not considering myself an expert in the field. These resources have significantly aided my understanding and performance in CP. It's important to note that the following recommendations are subjective and based solely on my personal experience

🔗 Video Lectures on DP (Helped me understand DP)

1. Errichto Lecture #1
   • Covers Fibonacci, iteration vs recursion
2. Errichto Lecture #2
   • Covers Coin change, double counting
3. Errichto Lecture #3
   • Covers Line of wines
4. Aditya Verma DP playlist - Watching till lecture #32 is enough!
   • Builds a solid foundation of DP using the the classical problems from depth

Note

Must watch! These are some of the best Dynamic Programming contents out there.

Classical Problems

Here are some of the must-do DP problems (these are some famous classical problems and most of the easy/medium DP problems we face are variations of these ones). If you face issues understanding the problems don’t hesitate to watch a tutorial on youtube about that particular problem.

1. 0/1 Knapsack problem
   • Knapsack variations:
     • Unbounded knapsack
     • Subset sum
     • Coin change
2. Longest Common Subsequence (LCS)
   • (LCS) variations:
     • Longest palindromic subsequence (LPS)
     • Minimum insertions to form a palindrome
3. Longest Increasing Subsequence (LIS)
   • (LIS) variations:
     • (LCS + LIS) variation
4. Grid DP
   • Minimum cost path in a grid
   • Count the number of paths in a grid
   • Count the number of unique paths in a grid (with obstacles)
5. Some famous problems
   • Edit distance
   • Minimum number of jumps to reach the end of an array
   • Count ways to reach the Nth stair

Important

Finally, when you’re done with these aforementioned classical problems, go to this link and solve at least 20 problems from this page (maintaining difficulty in increasing order). Once you're ready, dive into dynamic programming (DP) problems on platforms like Codeforces, Codechef, Atocoder choosing ones that match your current rating level. Good luck!

The Famous Atcoder DP contest

This is a good place to test your DP skills and learn something new as well besides having fun.

Footnote

While these resources have been immensely beneficial in my CP journey, I acknowledge that learning DP is a continuous process, and there's always more to explore and understand. It's essential to approach DP problems with patience, persistence, and a willingness to learn from both successes and failures.