Dynamic Programming
Last updated
Was this helpful?
Last updated
Was this helpful?
Dynamic Programming is a method for solving complex problems, that require solutions of the same sub-problems. It does this by breaking down the initial problem in sub-problem and then tries to find a solution for these sub-problems. Once it found this, it will store these solutions for re-use later.
We can think of it as a "carefully chosen brute force" which will try all the possibilities, but avoid having an exponential amount by limiting them.
Core ideas
Guessing (Try all the different choices and take the best one)
Recursion (Express the solution of a problem in terms of subproblems)
Memoization (Once we found an answer, store in a lookup table = write on memo pad, and re-use later)
Dynamic programming will basically express a problem as a Dynamic Acyclic graph (DAG) and find the shortest path in it
We can find the runtime for a dynamic programming problem by using the following formula:
We can break down every dynamic programming problem in a few steps which will help us to find a problem: 1. Define the subproblems and count them (#subproblems) 2. Guess (part of the solution), it is possible that there are no guesses. (#choices)
Example #1: In a knapsack problem we can choose between picking the item, or leaving it
Example #2: In Fibonacci there are no choices so = 1
Relate subproblem solutions (gets the time/subproblem)
Build an algorithm using one of the two techniques described. (make sure that subproblem is acyclic, so that we can use topological order)
Recurse & Memoize (Top-Down method): break down the given problem and solve + save it if it has not been solved yet. Return the saved answer
Build a DP table (Bottom-up method): Analyze the problem, find order in which sub-problems are solved and start solving from the trivial sub-problem. Up towards the given problem.
Solve the original problem
A quick tip on learning Dynamic Programming, is to think about the problems in a top-down fashion instead of bottom-up. We will however still program the problems in a bottom-up fashion, since it makes it easier to find the time and space complexity and results in a shorter source code.