Algorithm Design: Dynamic Programming Algorithms

Dynamic programming algorithms

Some algorithms break a problem into smaller subproblems and use the subproblems’ solutions to construct the larger one’s solution. During this process, the number of subproblems might become very large. Some algorithms solve the same subproblem repeatedly, needlessly increasing the algorithm’s runtime. Dynamic programming organizes computations to avoid re-computing already known values, which can often save a great deal of time.

Rocks game example

The Ringing Telephone Problem does not lend itself to a dynamic programming solution, so we consider a different problem to illustrate the technique. Suppose that instead of answering the phone, you decide to play the “Rocks” game with two piles of rocks, say ten in each. In each turn, one player may take either one rock (from either pile) or two rocks (one from each pile). Once the rocks are taken, they are removed from play. The player that takes the last rock wins the game. You make the first move. We encourage our learners to play this game using the interactive puzzle below:

To find the winning strategy for the $10 + 10$ game, we can construct a table, which we can call $R$, shown in Figure A. Instead of solving a problem with $10$ rocks in each pile, we will solve a more general problem with $n$ rocks in one pile and $m$ rocks in the other pile (the $n + m$ game) where $n$ and $m$ are arbitrary non-negative integers.