4 Steps to Solve Any Dynamic Programming (DP) Problem

FAANG Coding Interviews / Data Structures and Algorithms / Leetcode

[GregHogg]

Master Data Structures & Algorithms For FREE at AlgoMap.io!

[rohitkumaram]

4th step sometimes not possible, but yeah up to 3 definitely.

[sonicjoy]

very good summary of the step by step optimisation of DP problems, but it is hard for new learner to understand these 4 steps without a full blown explanation.

[azursmile]

Great video demonstrating progressive code refinement. Still not sure if the first step should be called "recursive backtracking". As discussed in previous video, think this is just "naïve recursion".

[yassinesafraoui]

What's complicated about DP IMO is figuring out what do the output depend on in such a way that it's memoizable, when facing new and complicated problems, It's not obvious at all

[Xrist]

I find that top-down solutions are easier to understand due to the decision tree nature of the solution as opposed to the bottom-up with dp that is sometimes harder to find the transition step.

[abiiranathan]

I think the memo dict would be a new one for each stack frame. I might be wrong. You are better off using lru_cache from functools or make the dict global

[kakimell]

I thought I was good with Python until I saw this video

[balasujithpotineni]

I feel like you just summed up one the first lecture on dynamic programming from an old mitocw series

[sarthakjain]

I can usually think of a top down approach but not the bottom up

[tomislam]

Hey Gregg, I'd love to see a deep dive into DP. Most importantly, I'd like to know how I can convert my naive approach progress from top-down to bottom-up to true dp solutions.
Thanks in advance.

[carlgauss]

5th solution, solve it on O(ClogN) where C depends on the dp specific recursion

[nihalbhamrah]

I dint understand 2nd one but other 3 were still understanable

[foerza]

How to do the 4th step in antoher algorithm? For example the knapsack?

[armandomendivil]

If we want to go little further we can take a look at the Golden ratio

[carlkarl]

i dont know about the caching thing thanks for telling and explaining

[abdallaalhag]

#4 should be optimized space complexity which includes O(1) for 1D DP instead of O(n) and O(n) for 2D DP instead of O(n^2)

[HeatCode]

Just for folks. 4th is not greedy approach. It’s still a dp based.

[Allthenameable]

To solve dp you should solve dp 3 times.
..got it

[hepotitus]

me* watches how to solve dynamic programming problems

also me* messes up f-strings