Introduction

Yes, bottom-up dynamic programming can absolutely be done in Lisp. The idea of bottom-up DP is language-independent: compute small subproblems first, store the results, and build toward the final answer iteratively. Lisp may be famous for recursion, but it also has arrays, loops, and mutable tables, which are exactly what bottom-up DP needs.

Bottom-Up DP Is About Data Flow, Not Syntax Style

A common misconception is that Lisp somehow implies top-down recursion only. In reality, bottom-up DP is just tabulation. If the algorithm benefits from iterating through states in a known order, Lisp can express that perfectly well.

The real question is which data structure fits the state space: a vector for integer-indexed states, a multidimensional array for grid problems, or a hash table when the state space is sparse.

A Simple Vector-Based Example

Fibonacci is not the most interesting DP problem, but it is a clean example of bottom-up tabulation.

1(defun fib-bottom-up (n)
2  (cond
3    ((= n 0) 0)
4    ((= n 1) 1)
5    (t
6     (let ((dp (make-array (+ n 1) :initial-element 0)))
7       (setf (aref dp 1) 1)
8       (loop for i from 2 to n do
9         (setf (aref dp i)
10               (+ (aref dp (- i 1))
11                  (aref dp (- i 2)))))
12       (aref dp n)))))
13
14(format t "~A~%" (fib-bottom-up 10))

This is textbook bottom-up DP: create the table, seed base cases, fill it in increasing order, and read the final result.

Lisp Arrays Fit Tabulation Naturally

For problems indexed by integers, Common Lisp arrays work well because they provide constant-time lookup and update.

1(defun ways-to-climb (n)
2  (let ((dp (make-array (+ n 1) :initial-element 0)))
3    (setf (aref dp 0) 1)
4    (loop for i from 1 to n do
5      (incf (aref dp i) (aref dp (- i 1)))
6      (when (>= i 2)
7        (incf (aref dp i) (aref dp (- i 2)))))
8    (aref dp n)))
9
10(format t "~A~%" (ways-to-climb 5))

That pattern generalizes well. Once your recurrence has a clear state order, Lisp's array operations are direct and efficient enough for iterative DP.

You Can Still Write It Idiomatically

Bottom-up does not mean "write C in parentheses". You can still use local helpers, descriptive state names, and data-structure choices that fit Lisp well.

For sparse state spaces, a hash table may be more natural than a dense array. For multidimensional DP, nested arrays or custom indexing functions can keep the code readable. Lisp gives you freedom here; it does not force one DP style.

That flexibility is one reason bottom-up DP works fine in Lisp. The language is expressive enough to support both mathematical clarity and pragmatic table mutation.

Choose Bottom-Up When Order Is Clear

Bottom-up DP is especially attractive when the dependency order is obvious and when you want predictable memory access. Top-down memoization is often easier to derive from a recursive recurrence, but bottom-up can be faster and easier to reason about in iterative state problems.

A good Lisp programmer should feel comfortable choosing either approach based on the problem rather than on myths about the language.

Space Optimization Also Works

Just because you start with a full table does not mean you must keep it forever. Many bottom-up DP algorithms only depend on a few previous states, so you can reduce memory use while staying iterative.

1(defun fib-optimized (n)
2  (cond
3    ((= n 0) 0)
4    ((= n 1) 1)
5    (t
6     (let ((a 0)
7           (b 1))
8       (loop repeat (- n 1) do
9         (psetq a b
10                b (+ a b)))
11       b))))

This is still bottom-up dynamic programming. The table has simply been compressed into the states you actually need.

Common Pitfalls

• Assuming Lisp forces top-down recursion and therefore cannot express bottom-up DP naturally.
• Using lists where arrays or hash tables would make state lookup much clearer.
• Ignoring base-case initialization, which makes the whole table wrong.
• Writing iterative DP in a way that obscures the dependency order.
• Forgetting that some DP tables can be space-optimized after the recurrence is understood.

Summary

• Bottom-up dynamic programming works perfectly well in Lisp.
• Lisp arrays and hash tables are natural storage choices for DP state.
• The core requirement is a valid dependency order, not any special language feature.
• Bottom-up and top-down are both viable in Lisp; choose based on the problem.
• Many bottom-up solutions can later be space-optimized without changing the overall approach.