Assume an equilateral triangle *T* of numbers. A **move** from any non-base
number *n* in *T* ends at the number immediately below and to the left or
right of *n*. A **path** in *T* is a sequence of moves starting at the
apex and ending at a number in the base. The **path sum** is the sum of the
numbers along a path. Given a triangle, find a path with maximum sum among all
paths through the triangle.

A brute-force solution is straightforward:

```
(define (max-sum-path triangle)
; Return a pair, the car of which is the path sum of the cdr, which
; is a max path through the given triange. A path is a list of 0s
; and 1s indicating left (0) or right (1) moves.
(let
((rows (1- (triangle 'row-count)))
(max-path '())
(max-sum -1))
(let loop
((row 0) (i 0) (path '()) (sum (triangle 'get-value 0 0)))
(if (< row rows)
; Above the base.
(let ((r (1+ row)))
; Let's go down and to the left.
(loop r i (cons 0 path) (+ (triangle 'get-value r i) sum))
; Now let's go down and to the right.
(let ((i2 (1+ i))
(sum' (+ (triangle 'get-value r i2) sum)))
(loop r i2 (cons 1 path) sum'))
; At the base; this path is done.
(if (or (null? max-path) (> sum max-sum))
(begin
(set! max-path path)
(set! max-sum sum)))))
(cons max-sum (reverse max-path)))))
```

A numeric triangle is a simple-object representing an equilateral triangle of numbers. For reasons explained below (and which you may have already anticipated), a numeric triangle is a wrapper around a general triangular matrix.

```
(define (numeric-triangle rows)
(let
((triangle (triangle-matrix rows)))
; Fill the triangle with random numbers.
(do ((r 0 (1+ r))) ((>= r rows))
(do ((i 0 (1+ i))) ((> i r))
(triangle 'set-value! r i (- (random 100) 50))))
(lambda (cmd . args)
(case cmd
((row-count) (triangle 'row-count))
((get-value) (apply triangle 'get-value args))
((set-value!) (apply triangle 'set-value! args))
(else (error "unrecognized command"))))))
```

A triangular matrix is represented as a vector of minimum necessary size. Perhaps the easiest way to understand the indexing is to imagine a triangle stored in a 2d matrix with all rows pushed to the left; that is, stored in a lower triangular matrix.

```
(define (triangle-matrix rows)
(define (gauss n) (/ (* n (1+ n)) 2))
(define (index r i) (+ (gauss r) i))
(let*
((row-count rows)
(N (gauss rows))
(values (make-vector N '()))
(get-value (lambda (r i) (vector-ref values (index r i))))
(set-value! (lambda (r i v) (vector-set! values (index r i) v))))
(lambda (cmd . args)
(case cmd
((row-count) rows)
((get-value) (apply get-value args))
((set-value!) (apply set-value! args))
(else (error "unrecognized command"))))))
```

This solution works, but isn't good because it's exponential in the number of rows in the triangle. Increasing the triangle size by five rows increases the solution run-time in usec by at least an order of magnitude; the solution run in Guile 1.8.1 on a fairly modern laptop takes over four minutes to find a path through a 25-row triangle.

The solution is slow because it repeatedly recomputes max-sum paths for sub-triangles. The fix for such problems is to use dynamic programming: once a max-sum path is found for a sub-triangle, remember it so the next time the max-sum path for that sub-triangle is needed, it can be found by indexing rather than more onerous computing.

Another trick to exploit is to find sub-triangle max-sum paths from the base up rather than from the apex down. This allows a third trick, which is to replace a full table with a pair of rows (as was done for edit-distance); for simplicity, however, this last trick will be skipped.

```
(define (max-sum-path-dp triangle)
; Return a pair, the car of which is the path sum of the cdr, which
; is a max path through the given triange. A path is a list of 0s
; and 1s indicating left (0) or right (1) moves.
(let* ((rows (triangle 'row-count))
(table (triangle-matrix rows)))
; Fill in the base
(let ((r (1- rows)))
(do ((i 0 (1+ i))) ((> i r))
(table 'set-value! r i
(cons (triangle 'get-value r i) '()))))
; Work up from the base to the apex, row by row. When done,
; return the max-sum path found at the apex.
(do ((row (- rows 2) (1- row))) ((< row 0) (table 'get-value 0 0))
; Within each row, work left to right (or right to left; it
; doesn't matter).
(do ((i 0 (1+ i))) ((> i row))
(let*
((row-below (1+ row))
(left (table 'get-value row-below i)) (l-max (car left))
(right (table 'get-value row-below (1+ i)))
(r-max (car right)))
(let ((v (triangle 'get-value row i)))
(table 'set-value! row i
(if (< r-max l-max)
(cons (+ l-max v) (cons 0 (cdr left)))
(cons (+ r-max v) (cons 1 (cdr right)))))))))))
```

The dynamic-programming version of max-sum-path solves a 25-row triangle in 9 msec and a 300-row triangle in 36 sec.