# COMP 105: Handout on dynamic programming

Dynamic programming is a generalization of iteration and recursion. All three techniques are based on mathematical induction.

• In an iterative or recursive program, you solve a problem of size n by first solving a subproblem of size n-1. Computing the factorial function falls into this category, and it can be done either iteratively or recursively. (This idea generalizes, e.g., to the Fibonacci function, where you need both n-1 and n-2 to solve n.)
• In a recursive program, you solve a problem of size n by first solving two subproblems of size n/2. Or, more generally, you solve a problem of size n by first solving a subproblem of size k and one of size n-k, where 1 < k < n. Quicksort and mergesort are two examples of this kind of problem, which can easily be programmed recursively, but is not so easy to program iteratively. (You essentially have to simulate recursion using an explicit stack.)
• In dynamic programming, you solve a problem of size n by first solving all subproblems of all sizes k, where k<n. Finding the shortest route from one point to another on the London Underground is an example of this kind of problem. (The London Underground is a multiply-connected graph, and you solve the problem by first finding all points for which the shortest path is 1 stop, then for which the shortest path is 2 stops, etc etc.)