What is dynamic programming?
- A technique for solving optimisation problems
- similar solution to divide and conquer except the recursive calls are replaced by reference to a table of values computed by subproblems of the original problem
How is a problem solved by dynamic programming?
- characterise the structure, key elements and parameters of the problem and how they related to each other
- define the value of the optimal solution recursively, express the optimal solution in terms of it’s subproblems
- define base cases (subproblems that can be solved directly/need no further decomposition)
- define a recurrence relation which tells us the relationship between subproblems
- Solve the subproblems and combine them to obtain the solution of the original problem
What type of problem are dynamic programming solutions used to typically solve?
Optimisation problems
- that have a maximising or minimising function
- applied where brute force is infeasible
What are the 3 features a problem must have to be effectively solved by dynamic programming?
- must be able to break the problem into subproblems with a similar structure
- the optimal solutions must be composed of the optimal solutions of subproblems
- optimal solutions to some subproblems can contain subproblems in common (overlap)
What is memoisation?
- Where computed values are stored in cache and later retrieved when they’re needed instead of recomputing them, in order to make applications more efficient/faster
What can make the run time of a dynamic programming solution poor?
Subproblems overlap and recompute the same value over and over which is inefficient
What is the naive dynamic programming runtime of calculating the fibonacci sequence?
O(2^n)
What is the dynamic programming memoisation run time of calculating the fibonacci sequence?
- Removing recalculating values and taking them from a table give us O(n^2)
What problems can we solve with dynamic programming?
- Calculating Fibonacci sequence
- {0,1} Knapsack Problem
- Weighted Interval Scheduling
What is the dynamic programming runtime of the solution for the {0,1} Knapsack problem?
O(n*W)
- where n is the number of elements to be packed
- and W is the max weight the knapsack can hold
- inefficient as run time is exponential as Wmax is exponential?
What is weighted interval scheduling?
- have a collection of tasks to schedule with a start and finish time but also a value Vi
- aim is to schedule a subset of non-conflicting tasks have the maximum total value
What is the time complexity for finding the weighted interval scheduling problem solution using dynamic programming?
O(n*logn) since we use memoisation
What can we use to prove that the dynamic programming solution for the weighted interval scheduling problem is correct?
We can use proof by induction
- since every succeeding task’s optimal solution can be calculated by the optimal solutions of preceeding tasks (computed and stored in the dynamic programming table),
- we can show that the induction base holds and then show the induction step also holds
