Indian Computing Olympiad

Dynamic Programming

Motivation

Suppose we arrange some numbers in the form of Pascal's triangle, like the following example:

                           15
                          /  \
                        28    33
                       /  \  /  \
                     18    22    16
                    /  \  /  \  /  \
                  35    15    11    17
                 /  \  /  \  /  \  /  \
               29    13    14    26    12
      

We want to start at the top number (the "root") and follow any path down the triangle to the bottom row (the "leaves"). What is the weight of the heaviest such path (that is, in terms of the sum of the numbers encountered along the path)?

The naive solution is to recursively find the weights of the heaviest paths from 28 and 33 to the leaves and then add 15 to the heavier of these two weights.

The problem is that this recursive computation recomputes the same quantity too many times. For instance, for both 28 and 33, we will compute the recursively compute the weight of the heaviest path from 22 to the leaves.

Here is a more efficient solution. Compute heaviest paths bottom-up and store the value at each node. To compute the heaviest path at a node, look up the heaviest path value stored at each of its children and add the current weight to the heavier of the two. Thus, a lower node's value is computed just once and reused by both its upper neighbours.

Dynamic programming

This is an example of dynamic programming.

We use dynamic programming when breaking up the original problem into subproblems yields overlapping subproblems. A naive recursive solution would result in wasteful recomputation of the same values. Instead, we solve the subproblems "bottom up" and store their values so that we can look them up whenever needed.

Computing Fibonacci numbers

The Fibonacci numbers are defined as the sequence F_1, F_2, … where F_1 = 1, F_2 = 1 and, for n > 2, F_n = F_{n-1} + F_{n-2}.

Suppose we compute F_8 recursively. This generates subproblems as follows:

                        F_8
                     /       \
               F_7              F_6
              /   \            /    \
           F_6     F_5      F_5      F_4
          /  \    /   \     /  \      /  \
       F_5  F_4  F_4  F_3  F_4 F_3  F_3  F_2
        .    .    .    .    .    .    .    .
        .    .    .    .    .    .    .    .

      

Observe that F_6 is computed twice, F_5 is computed 3 times, F_4 is computed 5 times, …

Instead, we can start from F_1 and F_2 and compute, in sequence, F_3, F_4, ... , F_8 avoiding wasteful recomputation. In fact, this is what we are doing instinctively when we normally enumerate the Fibonacci numbers as 1,1,2,3,5,8,…

Video lecture on Dynamic programming, NPTEL online course on Design and Analysis of Algorithms

• Dynamic programming (Lecture slides)

• Memoization (Lecture slides)