Dynamic Programming ( DP - 4 )

In the last 3 articles, we have discussed What is Dynamic Programming? How to solve  Dynamic Programming Problems and understood all the concepts from basic which is required for solving any Dynamic Programming Problems.

Image Src: Google

Now the only thing which we have to do is to practice problems of different types for the remaining 27 days article including this.

Now if you ask me why I have chosen " 30 days of Dynamic Programming "? The answer is this that in 21 days we can build/destroy any habit. As to solve DP problems our mindset should be developed to think in this way. So for this in the first three days, we have discussed the concepts, now let us practice.

Types of DP problems
  • 1 Dimensional DP problems. ( Example: Fibonacci Number )
  • 2 Dimensional DP problems. ( Example. Longest Common Subsequence )
  • 3 Dimensional DP problems. ( Example: Floyd-Warshall algorithm to find the minimum distance between (u,v) after K intermediate nodes )
1- dimensional DP problems.
These problems are solved using linear Data Structure like Array's, Dynamic Array's i.e. Vectors.
  1. Frog 1 ( AtCoder )
  2. Frog 2 ( AtCoder )
  3. Before an Exam ( 4B )
  4. Cheap Travels ( 466A )
  5. Flowers ( 474D )
  6. Given the length and sum of digits ( 489C )
  7. Woodcutters ( 545C )
  8. Number of ways ( 466C )
  9. Two Substrings ( 550A )
  10. Quasibinary ( 538B )
  11. Doraemon and WiFi ( 476B )
  12. Fence ( 363 B )
I hope that these problems will help you to get hang of Dynamic Programming and interest you towards this. Take your time and solve these problems to get better at DP. To discuss any of these problems you can always reach us at Slack and Join there. The next article with problems will be published after 3 days till then let us all solve problems and have a productive discussion.

If you have some content OR material related to this OR there is an error then do share them through the comment section for which we will be thankful to you.

Thank You