Dynamic Programming

General

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:

$runtime = \#subproblems * time/subproblem (treat~a~recursive~call~as~Θ(1))$

Steps to find a solution

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
1. Relate subproblem solutions (gets the time/subproblem)
2. 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.
1. 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.

Reference

PreviousRandomized Search Trees NextFibonacci

Last updated 6 years ago

Was this helpful?

Dynamic Programming

General

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:

runtime = \#subproblems * time/subproblem (treat~a~recursive~call~as~Θ(1))

Steps to find a solution

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.