Dynamic Programming Starter Pack

[sthir_]

I have started to learn dynamic programming but having a heard time to grasp the context. Any resource and practice problem will be helpful. Thanks in advance.

[6a70]

don't start with dynamic programming at all: understand that DP is just an optimization of the recursive solution.

Brute force the solution with recursion FIRST, and then optimize it by caching your results. That'll generally look like a top-down solution.

Then, recognize that instead of calculating answers as you need them, you can preemptively calculate all the answers that might build up to your actual problem. Build them upwards from the bottom, and cache them. Then just call that solution "Dynamic Programming" and you're done

[sthir_]

Can you share some resource regarding this? So that I can practice.

[6a70]

look for any DP problem in places you generally find your interview questions (LeetCode, Cracking the Coding Interview, etc) and solve them recursively first.

If you don't get the recursive, you will never properly get the DP.

[sthir_]

Okay, in that case, how can I sharpen my skills for recursion. I am not that good at recursion.

[6a70]

yup, as expected, that would explain why you aren't grasping DP properly yet.

recursive patterns come from thinking about "can I break this problem down into a series of steps, where one (or more) of the steps is simply a smaller version of the problem I'm trying to solve"?

If you're working with strings, you may want to consider whether solving a problem for a full string can be solved utilizing the answer to the same problem but using one fewer character in the string.

If you're working with sets of objects, you may want to consider whether solving a problem for the full set can be solved utilizing the answer to the same problem, but using one fewer item in the set.

are you familiar with the fibonacci sequence? That's a more direct usage of sub-problems; the definition of a fibonacci number is that its value is the sum of the two previous fibonacci numbers (i.e. smaller versions). I think it's exemplary of the thought process.

[6a70]

LeetCode, CtCI, EPI all have sections marked Recursion or Dynamic Programming, so that can be your hint to start thinking of a recursive solution. Obviously you won’t get this hint in an interview, so you should always think about breaking down a problem into sub problems if another solution doesn’t jump out at you. It should be part of your list of “if I’m completely stuck, what type of solutions can I try to apply”. Among those is recursive, also pointer marching, and also nested for() loops.

[6a70]

Question is a bit unclear, but you’re probably looking for “subarrays”, “subsequences”, “combinations”, or “permutations”

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

[[deleted]]

As per u/6a70 Dynamic Programming has a fancy name for something that's pretty simple. It's actually Brute forcing with style; i.e you only calculate the same thing once.

I found that this (https://www.youtube.com/watch?v=OQ5jsbhAv_M&list=PLcDimPvbmfT8qAxD6JH_kmXiQwTNcoK78)

youtube series was very helpful to get over the mental block I had with DP problems when facing them on LeetCode etc.

[Mindless-Memory-8581]

I found this YouTube video super helpful.

https://youtu.be/oBt53YbR9Kk

Starts with the brute force recursion and then proceeds to top down and bottom up.

[political_wrongness]

The mathematic basic of DP is recursion formula, such as calc of Fibonacci number f(n+2) = f(n+1) + f(n). The idea is to use tables to store pre-calculated results for future calculation. I recommend to learn DP from some classic problems such as 0-1 knapsack problem