Can a typical Lisp dialect solve problems using the bottom-up "dynamic programming" approach?
(Please note: I'm not talking about "memoization" which, as far as I understand, is trivial using any Lisp dialect. I'm really talking about bottom-up Dynamic Programming, where you build, for an example, your array bottom up and then use the elements you just introduced to compute the next ones.)
For example, using dynamic programming, the "0-1 knapsack" problem can be solved in pseudo-polynomial time for inputs on which any other method would fail.
An imperative (incomplete) solution is:
for (int k = 1; k <= a.length; k++) {
for (int y = 1; y <= b; y++) {
if (y < a[k-1]) {
knap[k][y-1] = knap[k-1][y-1];
} else {
if (y > a[k-1]) {
knap[k][y-1] = Math.max(knap[k-1][y-1], knap[k-1][y-1-a[k-1]] + c[k-1]);
} else {
knap[k][y-1] = Math.max(knap[k-1][y-1], c[k-1]);
}
}
Is such a thing possible to do in the various Lisp dialects? If no, why not?