Dynamic Programming

Note

Objectives

1. Identify whether a recursive algorithm can be rewritten using DP.
2. Explain how unique paths can be counted using recursion and DP.
3. Explain how a min-cost seam can be found using recursion and DP.

Graph data structures (like adjacency lists) and graph algorithms (like Dijkstra's algorithm) provided reusable abstractions for addressing many kinds of problems. But it's often the case that reusable solutions are not the most efficient solutions. If we choose to solve seam finding problems using shortest paths algorithms, then we will be limited by our most efficient algorithms for shortest paths problem like Dijkstra's algorithm.

How else might we design a solution for seam finding without relying on the shortest paths problem? Algorithm design paradigms like dynamic programming can help us develop more efficient solutions when greater efficiency is necessary.

Recursive algorithms

The Hemachandra sequence, also known as the Fibonacci sequence, is a series of numbers in which each number is the sum of the two preceding numbers starting with 0 and 1. We can represent this rule as a recurrence: $F(N) = F(N - 1) + F(N - 2)$ with the base cases $F(0) = 0$ and $F(1) = 1$. By converting this recurrence into a program, we can compute the N^th Hemachandra number:

public static long fib(int N) {
    if (N == 0 || N == 1) {
        return N;
    }
    return fib(N - 1) + fib(N - 2);
}

We can draw a recursion tree diagram to visualize the process for computing fib(N). Each node in the diagram represents a call to fib, starting from $F(N)$, which calls $F(N - 1)$ and $F(N - 2)$. $F(N - 1)$ then calls $F(N - 2)$ and $F(N - 3)$, and so forth. Repeated subproblems are highlighted in different colors. Ultimately, this recursive algorithm has an exponential order of growth, which makes it impractical to run on even a modest choice of N!

Top-down dynamic programming

To save time, we can reuse the solutions to repeated subproblems. Top-down dynamic programming is a kind of dynamic programming that augments a recursive algorithm with a data structure to cache (store) the result of each subproblem. Recursion is only used to solve each unique subproblem exactly once, leading to a linear time algorithm for computing the N^th Hemachandra number.

private static long[] F = new long[92];

public static long fib(int N) {
    if (N == 0 || N == 1) {
        return N;
    }
    if (F[N] == 0) {
        F[N] = fib(N - 1) + fib(N - 2);
    }
    return F[N];
}

Top-down dynamic programming is also known as memoization because it provides a way to turn multiple recursion with repeated subproblems into dynamic programming by remembering past results.

N	0	1	2	3	4	5	6
F(N)	0	1	1	2	3	5	8

Note

The data structure, F, is responsible for mapping each input to its respective result. In the case of fib, the input is an int and the result is a long. Because integers can be directly used as indices into an array, we chose to use a long[] as the data structure for caching results. But, in other programs, we may instead want to use some other kind of data structure like a Map to keep track of each input and result.

Bottom-up dynamic programming

Bottom-up dynamic programming is another type of dynamic programming that also uses the same data structure to store results. But bottom-up dynamic programming populates the data structure using iteration rather than recursion, requiring the algorithm designer to carefully order computations.

public static long fib(int N) {
    long[] F = new long[N + 1];
    F[0] = 0;
    F[1] = 1;
    for (int i = 2; i <= N; i += 1) {
        F[i] = F[i - 1] + F[i - 2];
    }
    return F[N];
}

What's in common between both approaches? We can say that dynamic programmming is an algorithm design paradigm for speeding-up algorithms that make multiple recursive calls by identifying and reusing solutions to repeated recursive subproblems.