(define fibonacci
  (lambda (feet)
    (cond ((= feet 0) 1)
          ((= feet 1) 1)
          (else (+ (fibonacci (- feet 1))       ;; sub-problem
                   (fibonacci (- feet 2)))))))  ;; sub-problem

(define fibonacci
  (lambda (n)
    (let ((table (make-vector n)))
      (define fibonacci
        (lambda (n)
          (cond ((= n 0) 1)
                ((= n 1) 1)
                (else (+ (fibonacci-subproblem (- n 1))       ;; sub-problem
                         (fibonacci-subproblem (- n 2)))))))  ;; sub-problem

      (define fibonacci-subproblem
        (lambda (n)
          (ensure-in-table! n)))

      (define ensure-in-table!
        (lambda (n)
          (or (vector-ref table n)
              (begin (vector-set! table n (fibonacci n))
                     (vector-ref table n)))))

      (vector-fill! table #f)
      (fibonacci n))))
      
(define from-to-do
  (lambda (start stop f)
    (if (> start stop)
        'done
        (begin (f start)
               (from-to-do (+ 1 start) stop f)))))

(define fibonacci-dp
  (lambda (n)
    (let ((table (make-vector n)))

      (define fibonacci
        (lambda (n)
          (cond ((= n 0) 1)
                ((= n 1) 1)
                (else (+ (vector-ref table (- n 1))       ;; sub-problem
                         (vector-ref table (- n 2)))))))  ;; sub-problem

      (define store-into-table!
        (lambda (n)
          (vector-set! table n (fibonacci n))))

      (from-to-do 0 (- n 1) store-into-table!)
      (fibonacci n))))