02. Framework for solving the DP Problem

1. a state is a set of variables that can sufficiently describe a scenario

1. 1. A function or data structure that will compute/contain the answer to the problem for every given state.
   1. Top-Down

      Annotations:

      • is closer to our natural way of thinking and it is generally easier to think of the recurrence relation if we start with a top-down approach.
      1. Recursive function
      2. Hashmap
   2. Bottom Up
      1. Nested for loops
      2. And An Array
2. 2. A recurrence relation to transition between states
   1. A recurrence relation is an equation that relates different states with each other.
   2. finding the recurrence relation is the most difficult part of solving a DP problem
3. 3. Base cases, so that our recurrence relation doesn't go on infinitely

1. Time Complexity: O(2ˆn)
2. It's actually a recursion

Annotations:

• You may notice that a hashmap is overkill for caching here, and an array can be used instead. This is true, but using a hashmap isn't necessarily bad practice as some DP problems will require one, and they're hassle-free to use as you don't need to worry about sizing an array correctly. Furthermore, when using top-down DP, some problems do not require us to solve every single subproblem, in which case an array may use more memory than a hashmap.

1. Time Complexity: O(n)