Dynamic Programming

Dynamic Programming

Dynamic programming is a branch of operations research: a mathematical method for optimizing decision processes. It is also a common algorithmic technique in computer science.

Its basic idea resembles divide and conquer. Break the problem into subproblems and solve them in an order where earlier solutions provide useful information for later ones.

For each subproblem, list the possible local solutions. Keep those that can lead to an optimum and discard the others. Solve the subproblems in sequence; the final subproblem solves the original problem.

The essence of dynamic programming is defining states and state transitions. By splitting the problem and expressing the relationships between states, a solution can be computed through a recurrence. For a typical dynamic-programming problem, clearly define its states and write the recurrence.

Climbing stairs

A staircase has 10 steps. Each move climbs either one or two steps. How many different ways lead to the top?

Taking one step each time gives [1, 1, 1, 1, 1, 1, 1, 1, 1, 1]. Taking two steps each time gives [2, 2, 2, 2, 2]. Many other ways are possible.

Brute-force enumeration uses combinatorial reasoning and nested loops to visit every possibility, but takes exponential time. Is there a more efficient solution?

Perhaps find some stairs and try walking them—some exercise might help too!

Dynamic programming solves a decision problem in stages. It is used not only in programming but also in management, economics and biology. The broad idea is to break a large problem into manageable smaller ones.

Suppose only the last move remains before reaching step 10. What can happen?

There are two possibilities: the last move comes from step 9 or step 8, because each move climbs one or two steps.

If X ways lead from step 0 to step 9 and Y ways lead to step 8, then X + Y ways lead to step 10.

Let F(10) denote the number of ways to climb 10 steps. Then F(10) = F(9) + F(8). How do we calculate F(9) and F(8)?

The same reasoning gives F(9) = F(8) + F(7) and F(8) = F(7) + F(6). We simplify a complex problem in stages until only simple cases remain. This is the idea behind dynamic programming.

For one and two steps, there are one and two ways respectively. Therefore:

Three important concepts in dynamic programming are:

• Optimal substructure

• Boundaries

• A state-transition equation

In F(10) = F(9) + F(8), F(9) and F(8) are two subproblems. Stair climbing is a counting problem: partition the ways by their last move and add the disjoint counts, rather than choosing an optimum among solutions.

For one or two steps, the answer is known directly. F(1) and F(2) are the boundary cases. Without boundaries, this reduction would never reach a finite result.

F(n) = F(n−1) + F(n−2) is the state-transition equation. It is the core relationship between one stage and the next.

With the recurrence and boundaries established, we can implement it recursively.

Climbing stairs: recursion

#include <stdio.h>

int climb_recursive(int n) {
    if (n <= 0) {
        return 0;
    } else if (n == 1) {
        return 1;
    } else if (n == 2) {
        return 2;
    }
    return climb_recursive(n - 1) + climb_recursive(n - 2);
}

Recursion calculates the answer, but its running time is exponential.

The number of nodes in the recursion tree is the number of computations, giving an $O(2^n)$ time bound.

Some arguments are calculated repeatedly, with more duplication deeper in the tree.

Must F(n) be evaluated recursively from the top down? A bottom-up iteration can also produce the answer.

We already know F(1) = 1 and F(2) = 2:

Since F(3) = F(1) + F(2), one iteration produces F(3).

The second iteration computes F(4) using only F(2) and F(3). F(3) was calculated previously, so it need not be repeated.

Climbing stairs: dynamic programming

#include <stdio.h>

int climb_dp(int n) {
    if (n <= 0) {
        return 0;
    } else if (n == 1) {
        return 1;
    } else if (n == 2) {
        return 2;
    }

    int num1 = 1;
    int num2 = 2;
    int sum;
    for (int i = 3; i <= n; i++) {
        sum = num1 + num2;
        num1 = num2;
        num2 = sum;
    }
    return sum;
}

The code accepts a nonnegative integer n and returns 0 when n≤0. The example counts fit the integer range.