Zusammenfassung der Ressource
02. Framework for solving the DP
Problem
- State
- a state is a set of variables that can sufficiently describe a scenario
- Solving DP
- 1. A function or data structure that will compute/contain the answer to the problem for every given
state.
- Top-Down
Anmerkungen:
- 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.
- Recursive function
- Hashmap
- Bottom Up
- Nested for loops
- And An Array
- 2. A recurrence relation to transition between states
- A recurrence relation is an equation that relates different states with each other.
- finding the recurrence relation is the most difficult part of solving a DP problem
- 3. Base cases, so that our recurrence relation doesn't go on infinitely
- If no memoization
- Time Complexity: O(2ˆn)
- It's actually a recursion
- With Memoization
Anmerkungen:
- 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.
- Time Complexity: O(n)