Computer Algorithms II Lecture Notes

4 September 2007 • Introduction

That an N-row triangle has 2^{N - 1} paths suggests an alternative representation for paths: 2^{N - 1}-bit numbers with 0 representing down and to the left and 1 representing down and to the right (or vice versa; it doesn't matter).

The binary-number path representation simplifies the algorithm:

max-sum-path(triangle)

  max-path = 0
  max-sum = path-sum(triangle, max-path)

  for path = 1 to 2N - 1
    sum = path-sum(triangle, path)
    if sum > max-sum
      max-sum = sum
      max-path = path

  return [ max-sum, max-path ]

This page last modified on 24 January 2006.