Dynamic Programming Flashcards
Which class of problems can DP solve efficiently?
Optimization problems. Like minimizing something, maximizing something, best of something etc. Some examples are Shortest Path, Maximum subsequence of two strings, Knapsack etc.
Which are two ways to solve DP problems?
Bottom Up or Top Down
Define Bottom Up approach to DP?
You compute base case first and store that in table and then next moves are dependent on base case. You compute dp[0] first, dp[1] and then till dp[n]. dp[n] is our answer. So all subsequent steps are dependent on some calculation we have already performed.
Define Top Down approach to DP?
Recursion based solution. dp(n) -> dp(n-1) -> … dp(0).
Which is the first step to solve a DP problem
?
First step is to figure out subproblems which can help to solve the original problem. They don’t have to be same as original problem at hand, but should somehow help in achieving to the solution. Then memoize the answer to subproblem so that if we have to solve it again we can reuse the answer.
Running time of DP problem?
No of subproblems * Time to solve each subproblem. So for fibonacci the running time will be n (subproblems) * O(1) constant time per subproblem (multiplication). Here we ignore the recursive call overhead (for the memoized calls).
What kind of sort are we doing for subproblems in DP?
We are doing a “topological sort” of the subproblems in the DAG (Directed Acyclic Graph) of subproblem dependency.
How much space do you need for memoization of fibonacci?
If we create a DAG and write code you will realize that you only need to remember last two values. So we can achieve in constant space and linear time.
Which is a tool that you have when you don’t know the answer but you would like to know?
Guessing. Guess and optimize for the best guess. So we guess but intelligently. Algorithmically we don’t just guess one, we guess all guesses. So this is similar to Brute Force but carefully.
Which are the central concepts in DP?
DP is equivalent to recursion+ memoization + guessing
Which is the one thing needed for memoization to work?
Its that the subproblem dependencies should be acyclic. Otherwise we get an infinite algorithm.
