DP Flashcards
Does DP explore all possible solutions?
Yes
What are characteristics of DP problems?
1) The problem can be broken down into “overlapping subproblems”
2) The problem as “optimal substructure”
What is an overlapping subproblem?
Smaller versions of the original problem whose answer can be reused
What is optimal substructure?
An optimal solution can be found by combining the optimal results from the overlapping subproblems of the original problem.
Is divide and conquer DP?
No because the subproblems are not overlapping.
What does memoizing a result mean?
Store the result of a function call, usually in a hash map, so that we can quickly return the cached results instead of recalculating.
Advantage of bottom-up DP?
implementation is usually faster as iteration if faster than recursion
Advantage of top-down DP?
Usually easier to write as we don’t need to consider the order of the subproblems.
What is tabulation?
bottom-up DP
What is memoization
top-down DP
In general how do we know to use a DP algorithm?
If the problem is asking for a min/max/number and if future decisions are effected by past decisions, use DP. Otherwise it is probably greedy.
In general how do we know to use a DP algorithm?
If the problem is asking for a min/max/number, then likely DP or greedy. Then if future decisions are effected by past decisions, use DP. Otherwise it is probably greedy.
