Introduction to dynamic programming

Dynamic Programming basics

When should we use dynamic programming

1. If the problem has smaller sub problems consider putting dynamic programming or 2 functions needs to be called.
2. If the problem has 2 paths, then dp can be applied, such that we might be able to reuse the results generated from one path
3. Something related to optimal will be asked, like min, max, largest, smallest

How to write DP

1. Think about base condition
2. Write the recursive solution
3. Memoization of the solution - practice multiple times how to write Memoization
4. Then write top down approach, In fact, without memoization, this isn’t actually dynamic programming - it’s just basic recursion.
5. Memoization means caching the results. This is usually done with a hashmap or an array.

DP has lot of follow up problems which can be solved if you know its parent dp problem well.

Famous DP problem