Computer Algorithms: Dynamic Programming

Dynamic programming is a method of solving problems by breaking them into smaller sub-problems and solving each of these.

Consider the Towers of Hanoi problem: we have three pegs and disks of various sizes stacked from largest at the bottom and smallest at the top (each one has a hole in the center). This is depicted in the diagram below. The goal is to move the stack of disks from peg $A$ to peg $B$. But there's a catch: we cannot put a larger disk on top of a smaller disk.

We will solve this with dynamic programming. In fact, let's say we want to program that solves the Towers of Hanoi problem in $T(n)$ steps, where $n$ is the number of disks initially. How can we break this into smaller sub-problems?

Well, if we can find a way to transfer the bottom disk to $B$, then we will be able to solve it in $T(n-1)$ steps. However, there is one easy way to do this: move the first $n-1$ disks to $C$, then move the bottom one to $B$, then move the disks from $C$ to $B$. This will take $T(n)=T(n-1)+1+T(n-1)=2T(n-1)+1$ steps. Also, $T(1)=1$, so it's easy to see we can solve the problem in $T(n)=2^n-1$ steps!