7 Step Process

Dynamic Programming

• DP = recursion +memoization

1. MINIMUM NUMBER OF OPERATIONS
2. MAXIMUM NUMBER OF SOMETHING
3. DEPTH FIRST SEARCH CAN BE IMPLEMENTED WITH THIS
4. NUMBER OF DIFFERENT WAYS TO SOLVE SOMETHING

• HOW TO APPROACH

1. Identify the base cases for the larger problem, the smallest possible subproblem you can encounter
   1. ALSO STATE SOME POTENTIAL EDGE CASES—USE FOR VERIFICATION AFTER FIRST PASS AT CODE
2. Come up with a generic example and then state and talk through the brute force algorithm
   1. Break it down into subproblems and then see how you have to change pointers, what to pass to subsequent calls
   2. Start writing pseudocode as you talk through this
3. State that because its a recursive solution using dynamic programming(memoization) would optimize this
4. Try to determine whether its bottom up or top down DP
   1. BOTTOMS UP
      1. You are computing the smallest possible subproblems and then comparing or combining them as you move back up the recursive stack to the largest subproblem
5. Determine how the cache or data structure used for memoization is going to store it- verify the runtime here
6. start debugging- verify with edge cases and examples

Recursion