Memoised and Tabulated Solutions in Python, Java and TypeScript

The stall problem written both ways in each language, printing the same answer.

The no-neighbours stall problem can be written top-down with a memo or bottom-up with a table, and the listings below give both in each language. Each solves the four stalls from Define a State and a Recurrence, Then Check Them by Hand and a row of 900 stalls, whose takings are generated as (i × 37) mod 11 so the run repeats exactly.

Both forms use a small trick to drop the base cases: best(i) for i below 0 is 0, the total from no stalls, so the recurrence works from the first stall onwards. The table version shifts its indices by two to hold those two zeros.

The stall problem with a memo and with a table, in each language

dp_code.pypy

from functools import cache


def best_memoised(takings: list[int]) -> int:
    @cache
    def best(i: int) -> int:
        if i < 0:
            return 0
        return max(best(i - 1), best(i - 2) + takings[i])

    return best(len(takings) - 1)


def best_tabulated(takings: list[int]) -> int:
    table = [0] * (len(takings) + 2)
    for i, value in enumerate(takings):
        table[i + 2] = max(table[i + 1], table[i] + value)
    return table[-1]


small = [3, 2, 7, 10]
long = [(i * 37) % 11 for i in range(900)]
for name, takings in (("3 2 7 10", small), ("900 stalls", long)):
    print(f"{name}: memoised {best_memoised(takings)}, tabulated {best_tabulated(takings)}")

OutputRan with python:3.14.8-slim-trixie (Python 3.14.8)

3 2 7 10: memoised 13, tabulated 13
900 stalls: memoised 2781, tabulated 2781

DpCode.javajava

import java.util.HashMap;
import java.util.Map;
import java.util.stream.IntStream;

public class DpCode {
    static int bestMemoised(int[] takings) {
        Map<Integer, Integer> memo = new HashMap<>();
        return best(takings, takings.length - 1, memo);
    }

    static int best(int[] takings, int i, Map<Integer, Integer> memo) {
        if (i < 0) {
            return 0;
        }
        Integer known = memo.get(i);
        if (known != null) {
            return known;
        }
        int value = Math.max(best(takings, i - 1, memo), best(takings, i - 2, memo) + takings[i]);
        memo.put(i, value);
        return value;
    }

    static int bestTabulated(int[] takings) {
        int[] table = new int[takings.length + 2];
        for (int i = 0; i < takings.length; i++) {
            table[i + 2] = Math.max(table[i + 1], table[i] + takings[i]);
        }
        return table[table.length - 1];
    }

    public static void main(String[] args) {
        int[] small = {3, 2, 7, 10};
        int[] longer = IntStream.range(0, 900).map(i -> (i * 37) % 11).toArray();
        System.out.println("3 2 7 10: memoised " + bestMemoised(small) + ", tabulated " + bestTabulated(small));
        System.out.println("900 stalls: memoised " + bestMemoised(longer) + ", tabulated " + bestTabulated(longer));
    }
}

OutputRan with eclipse-temurin:25.0.4.1_1-jdk-noble (Java 25.0.4.1)

3 2 7 10: memoised 13, tabulated 13
900 stalls: memoised 2781, tabulated 2781

dp_code.tsts

function bestMemoised(takings: number[]): number {
  const memo = new Map<number, number>();
  const best = (i: number): number => {
    if (i < 0) {
      return 0;
    }
    const known = memo.get(i);
    if (known !== undefined) {
      return known;
    }
    const value = Math.max(best(i - 1), best(i - 2) + takings[i]);
    memo.set(i, value);
    return value;
  };
  return best(takings.length - 1);
}

function bestTabulated(takings: number[]): number {
  const table = new Array<number>(takings.length + 2).fill(0);
  takings.forEach((value, i) => {
    table[i + 2] = Math.max(table[i + 1], table[i] + value);
  });
  return table[table.length - 1];
}

const small = [3, 2, 7, 10];
const long = Array.from({ length: 900 }, (_, i) => (i * 37) % 11);
for (const [name, takings] of [["3 2 7 10", small], ["900 stalls", long]] as const) {
  console.log(`${name}: memoised ${bestMemoised(takings)}, tabulated ${bestTabulated(takings)}`);
}

OutputRan with node:24.22.0-trixie-slim (Node 24.22.0), TypeScript 5.9.3

3 2 7 10: memoised 13, tabulated 13
900 stalls: memoised 2781, tabulated 2781

All three printed the same lines, and a separate check that tries every valid choice of the four stalls, and solves the 900 with a different recurrence, printed them too.

The highlighted lines are where each form keeps its answers. Python's memo is functools.cache, a decorator that stores each result under its arguments, so the recursive function is the recurrence and nothing else; it needs arguments that can be dictionary keys. Java and TypeScript have no built-in equivalent, so the memo is a HashMap or a Map read before the work and written after it. Java's lookup returns null for a missing key, which is why known is an Integer rather than an int. The third highlighted line in each is the bottom-up step: one entry from the two before it.

The 900 stalls are a deliberate size. Python allows 1,000 nested calls by default, and the memoised version nests about one call per stall, so 900 fits and a few thousand would not. Memoisation vs Tabulation runs both forms on a million stalls.

← → move through sections and cards