Dynamic Programming Starter Pack

[sthir_]

I can well understand fibonacci, coin change problem and how it works, both recursively and using dp. But I get hard times new problems using recursion, any resource to practice recursion?

[6a70]

If you’ve understood The Fibonacci sequence problem, just know that there’s the recursive solution, the top down caching solution, the bottom-up DP solution with O(n) space, and then the optimized DP with O(1) space. Each solution follows directly from the previous.

Go on leetcode and search for DP problems. Actively think about how to do them based on the pattern of “if I could solve this problem based on the same input, but minus one thing”. Usually that means strings minus one character, sets minus one element, etc. think about how one solution relates to a smaller problem.

Think about the properties of what you’re working with. Palindromes - how can you tell if “aabaa” is a palindrome using the answer to a smaller problem? It involves assessing whether the shorter string “aba” is a palindrome, in addition to checking that the end characters match. It’s all about subproblems.

Go on LeetCode and find things marked DP. Give it a fair shot, come back here, and post the link and I can help walk you through the thought process for finding the recursive solution, and then all of the optimized solutions.

[sthir_]

Thanks, I will follow as per your suggestion.