(define (make-table m n)
  (let ((table (make-vector 2)))
    (vector-set! table 0 n)
    (vector-set! table 1 (make-vector (* m n)))
    table))

(define (table-set! table i j value)
  (vector-set! (vector-ref table 1)
               (+ j (* i (vector-ref table 0))) value))

(define (table-ref table i j)
  (vector-ref (vector-ref table 1)
              (+ j (* i (vector-ref table 0)))))

(define (table-fill! table value)
  (vector-fill! (vector-ref table 1) value))

(define (choose n k)
  (cond ((= k 0) 1)
        ((= n k) 1)
        (else (+ (choose (- n 1) k)
                 (choose (- n 1) (- k 1))))))

(define (choose n k)
  (let ((table (make-table n (+ k 1))))
    (define (choose n k)
      (cond ((= k 0) 1)
            ((= n k) 1)
            (else (+ (choose-subproblem (- n 1) k)
                     (choose-subproblem (- n 1) (- k 1))))))

    (define choose-subproblem
      (lambda (n k)
        (ensure-in-table! n k)))
    
    (define ensure-in-table!
      (lambda (n k)
        (or (table-ref table n k)
            (begin (table-set! table n k (choose n k))
                   (table-ref table n k)))))

    (table-fill! table #f)
    (choose n k)))
    
(define (choose n k)
  (let ((table (make-table n (+ k 1))))
    (define (choose n k)
      (cond ((= k 0) 1)
            ((= n k) 1)
            (else (+ (choose-subproblem (- n 1) k)
                     (choose-subproblem (- n 1) (- k 1))))))

    (define choose-subproblem
      (lambda (n k)
        (table-ref table n k)))

    (define store-into-table!
      (lambda (n k)
        (table-set! table n k (choose n k))))

    (from-to-do 0 (- n 1)
                (lambda (n)
                  (from-to-do 0 (min k n)
                              (lambda (k)
                                (store-into-table! n k)))))
    (choose n k)))