(load "2d-table.scm")

;; compute the nth Fibonacci number using dynamic programming
(define dpf
  (lambda (n)
    (do ((T (make-vector (+ n 1)))
         (i 0 (+ i 1)))
      ((> i n) (vector-ref T n))
      (vector-set! T i
                     (if (< i 2)
                         i
                         (+ (vector-ref T (- i 1))
                            (vector-ref T (- i 2))))))))

;; This procedure computes choose(n, k) using dynamic programming,
;; filling the table row by row.
(define dpchoose
  (lambda (n k)
    (do ((T (make-table (+ n 1) (+ k 1)))
         (i 0 (+ i 1)))
      ((> i n) (table-ref T n k))
      (do ((j 0 (+ j 1)))
        ((> j (min i k)))
        (table-set! T i j
                    (cond ((zero? j) 1)
                          ((= i j) 1)
                          (else (+ (table-ref T (- i 1) j)
                                   (table-ref T (- i 1) (- j 1))))))))))