4. DP summary #

Created Thursday 12 March 2020

With a basic observation of what was happening vs what should happen, we can do wonders. Dynamic Programming is really very clever and easy programming.

• Make a bruteforce recursive solution.
• Make a memoized.

Steps to follow:

1. Make an array.
2. Initialize it if required, i.e for visited or unvisited mostly.
3. Enter the concrete values into the array
4. Decide the relationship between the answers and the question.
   1. What is the dependency.
   2. Is it counting or optimum. Here we check for the min or just add in case of counting.
   3. Are there multiple ways to reach the same answer, does it give the wrong thing, duplicacy etc. Partly covered in counting vs optimum.
   4. Can values be skipped, this will drastically reduce the array size.
   5. Write it iteratively.
   6. Most solutions give O(n) both space and time. Time is O(kn) in most case for some case/constraint dependent n;