Dynamic Programming - Basics

0) Greedy is Wrong

Before we start on a dynamic programming solution, we should make sure that no simpler solution strategy works. A first candidate is often “Greedy”, which means taking the best local number. In the above example, we would return the path 7,8,1,7,5, which has only the value 28. So worse than the best solution and therefore wrong.

1) Characterize the structure of an optimal solution

Let’s think about what characterizes an optimal solution. In every step we go one row lower and one to the left or right. Now let’s consider the final step in the optimal solution.

    .
   . .
  . . .
 2 7 . .
. 5 . . .

The field with the 5 can only be reached by passing either 2 or 7 in the previous step. This applies to every path up to the 5, i. e. especially to an optimal path up to the 5. We have seen in the example above that the optimal path to 5 comes from 7. Then what do we know about the partial path from the tip of the triangle to the 7? Among all paths from start to 7, this path must be one with maximum sum. Why? There is a “Cut & Paste” argument: If this were not the case, there would be a path from the top to the 7 with a higher sum. But then we could find with this path a better path to the 5 altogether, by extending this better path which goes to 7. However, this is a contradiction because we have based our assumptions on an optimal solution.

In other words, an optimal solution up to 5 must always consist of an optimal solution to one of its two possible predecessor fields. We will use this insight in the next step.

2) Recursively define the value of an optimal solution

Let’s try to formulate the problem recursively. Let $opt (i, j)$ be the maximum sum of a path from the tip of the triangle to the field $(i, j)$, this is the $j$-th field in the $i$-th row. For example, the $8$ in the third row is the $(3,1)$ field. The solution (the value of the best path from the top to any field in the bottom line) would then be the maximum of the opt fields in the last line:

How can $opt (i, j)$ be calculated? So we’ll figure out how to get to the $ (i, j)$ field? Either from the field to the right of $ (i - 1, j)$ or to the left of $ (i - 1, j - 1)$ in the line above. Since we know from 1) that an optimal path must consist of an optimal partial path to one of its two predecessor fields, we can now specify $opt (i, j)$ directly: it is the better of the two optimal paths to the predecessors. So:

where $T[i][j]$ indicates the number in the pyramid of the field $ (i, j)$. For the start field $ (1,1)$ itself there is only one path (which is of course the optimal one up to there):

This recursive formulation can be translated almost directly into code. Here is an example implementation in C++ (we change the numbering of the fields so that it now starts at 0 instead of 1).

std::vector<std::vector<int>> T = {
{     7       },
{   3,  8     },
{  8, 1,  0   },
{ 2, 7, 4, 5  },
{4, 5, 2, 6, 5}};

// Return the value of an optimal path until the field in
// line i and column j.
int MaximumTriangularSumPathRecursive(int i, int j) {
  // The top of the pyramid.
  if (i == 0 && j == 0) {
    return T[i][j];
  }
  int left = 0;
  int right = 0;

  // All fields on the very left have no left predecessor.
  if (j > 0) {
    left  = MaximumTriangularSumPathRecursive(i - 1, j - 1);
  }
  // All fields on the very right have no right predecessor..
  if (j < i) {
    right = MaximumTriangularSumPathRecursive(i - 1, j);
  }
  return std::max(left, right) + T[i][j];
}

Task for the reader: What is the runtime of this recursive solution? Does the program still find a solution in the foreseeable future for a triangle with 100 lines?

3) Compute the value of an optimal solution in a bottom-up fashion

Spoiler Alert: The program will not be able to finish in a reasonable time, because the runtime is $O (2^n)$ (exponential) and therefore for $n=100$ the number of operations is much too high (a further task for the reader: How to calculate the runtime of $O (2^n)$)?

What now? Well, the solution is of course Dynamic Programming. This time we choose a Bottom Up solution directly, but I would like to point out that memoization would also work.

For the calculation we use an array $opt[n][n]$ and calculate the solution step by step. This means that we start at the top of the pyramid (where there is only one path), and work our way down row by row. This means that we have already processed all rows

when editing the ith line, and can therefore use the recursive description of the solution from 2).

std::vector<std::vector<int>> T = {
{     7       },
{   3,  8     },
{  8, 1,  0   },
{ 2, 7, 4, 5  },
{4, 5, 2, 6, 5}};

// return value of an optimal path from the tip to the base
int MaximumTriangularSumPathBottomUp() {
  const int n = T.size();
  vector<vector<int>> opt(n, std::vector<int>(n));
  opt[0][0] = T[0][0];
  for (int i=1; i < n; i++) {
    for (int j=0; j<=i; j++) {
      if (j == 0) {
        // left border.
        opt[i][j] = T[i][j] + opt[i-1][j];
      } else if (j == i) {
        // right border.
        opt[i][j] = T[i][j] + opt[i-1][j-1];
      } else {
        opt[i][j] = T[i][j] + max(opt[i-1][j], opt[i-1][j-1]);
      }
    }
  }
  // the function max_element in <algorithm> returns an iterator to the
  // biggest element and the star dereferences
  // the iterator (takes the value of the iterator).
  return *std::max_element(opt[n-1].begin(), opt[n-1].end());
}

How fast is this solution? We note that we only have a constant amount of work for each field of the pyramid. Since there are $\frac{n^2}{2}$ fields, the runtime is $O (n^2)$ (i. e. linear in the input size, since we also have $O (n^2)$ many numbers in the input for a pyramid of the height $n$).

Construct an optimal solution from computed information

We now have an efficient solution to find the value of the optimal path and depending on the task, we are done. But this may not be enough, and we want to be able to calculate the value of an optimal path as well as the path itself. To do this, we first find the end of the optimal path (as derived from above, it is the maximum of the fields of the last line). Then we look backwards to see from which field the optimal value was reached, and walk backwards from the bottom to the top of the pyramid. The solution should become clearer in the following code:

// T = as above...
// return a optimal path for T as a vector of length n, where
// path[i] is the used field of the i-th row.
std::vector<int> MaximumTriangularSumPathBottomUpWithPath() {

  // as above...

  // the path consists of the fields with coordinates
  //   (0, path[0]), (1, path[1]), ..., (n-1, path[n-1])
  std::vector<int> path(n);

  // find the field in the last row in which the optimal path ends.
  // As above std::max_element returns an iterator to this field,
  // and std::distance returns the distance between the first element
  // and this iterator (which is the column index of the field beginnig with zero),
  path[n-1] = std::distance(opt[n-1].begin(), std::max_element(opt[n-1].begin(), opt[n-1].end()));

  for (int i=n-2;i>=0;--i) {
    if (path[i+1] == 0) {
      // left most field only has one possible predecessor.
      path[i] = 0;
    } else if (path[i+1] == i+1) {
      // right most field only has one possible predecessor.
      path[i] = i;
    } else {
      if (opt[i+1][path[i+1]-1] > opt[i][path[i+1]]) {
        // value comes from the right predecessor
        path[i] = path[i+1] - 1;
      } else {
        // value comes from the left predecessor.
        path[i] = path[i+1];
      }
    }
  }
  return path;
}