Dynamic programming: from recursion to tables

Python 3.14 · main.py

def plain(n: int, k: int) -> tuple[int, int]:
    """C(n, k) by Pascal's rule, and how many calls it took."""
    if k == 0 or k == n:
        return 1, 1
    left, left_calls = plain(n - 1, k - 1)
    right, right_calls = plain(n - 1, k)
    return left + right, left_calls + right_calls + 1


def memo(n: int, k: int, seen: dict[tuple[int, int], int]) -> tuple[int, int]:
    """The same recursion with a memo of the states worked out."""
    if k == 0 or k == n:
        return 1, 1
    if (n, k) in seen:
        return seen[(n, k)], 1
    left, left_calls = memo(n - 1, k - 1, seen)
    right, right_calls = memo(n - 1, k, seen)
    seen[(n, k)] = left + right
    return left + right, left_calls + right_calls + 1


def table(n: int, k: int) -> tuple[int, int]:
    """C(n, k) bottom-up in one row, counting its updates."""
    row = [1] + [0] * k
    updates = 0
    for i in range(1, n + 1):
        # Right to left, so row[j - 1] still holds row i - 1 when row[j] reads it.
        for j in range(min(i, k), 0, -1):
            row[j] += row[j - 1]
            updates += 1
    return row[k], updates


value, calls = plain(20, 10)
print(f"plain recursion: C(20, 10) = {value} after {calls} calls")
for n, k in [(20, 10), (30, 15)]:
    seen: dict[tuple[int, int], int] = {}
    value, calls = memo(n, k, seen)
    print(
        f"memo: C({n}, {k}) = {value} after {calls} calls, {len(seen)} answers stored"
    )
    value, updates = table(n, k)
    print(f"one-row table: C({n}, {k}) = {value} after {updates} updates")

In Python: Each function returns a (value, work) tuple, so no global counter is needed; in real code functools.cache and math.comb do the same in one line each.

Recorded with CPython 3.14.8 on macOS 26 arm64. It runs in your browser with Pyodide 314.0.7 (CPython 3.14.2). To run it yourself: python3 main.py

JavaScript Node 24 · main.mjs

// C(n, k) by Pascal's rule, and how many calls it took.
function plain(n, k) {
  if (k === 0 || k === n) return [1, 1];
  const [left, leftCalls] = plain(n - 1, k - 1);
  const [right, rightCalls] = plain(n - 1, k);
  return [left + right, leftCalls + rightCalls + 1];
}

// The same recursion with a memo of the states worked out.
function memo(n, k, seen) {
  if (k === 0 || k === n) return [1, 1];
  const key = `${n},${k}`;
  if (seen.has(key)) return [seen.get(key), 1];
  const [left, leftCalls] = memo(n - 1, k - 1, seen);
  const [right, rightCalls] = memo(n - 1, k, seen);
  seen.set(key, left + right);
  return [left + right, leftCalls + rightCalls + 1];
}

// C(n, k) bottom-up in one row, counting its updates.
function table(n, k) {
  const row = [1, ...new Array(k).fill(0)];
  let updates = 0;
  for (let i = 1; i <= n; i++) {
    // Right to left, so row[j - 1] still holds row i - 1 when row[j] reads it.
    for (let j = Math.min(i, k); j > 0; j--) {
      row[j] += row[j - 1];
      updates++;
    }
  }
  return [row[k], updates];
}

const [value, calls] = plain(20, 10);
console.log(`plain recursion: C(20, 10) = ${value} after ${calls} calls`);
for (const [n, k] of [
  [20, 10],
  [30, 15],
]) {
  const seen = new Map();
  const [memoValue, memoCalls] = memo(n, k, seen);
  console.log(
    `memo: C(${n}, ${k}) = ${memoValue} after ${memoCalls} calls, ${seen.size} answers stored`,
  );
  const [tableValue, updates] = table(n, k);
  console.log(`one-row table: C(${n}, ${k}) = ${tableValue} after ${updates} updates`);
}

In JavaScript: A Map needs a key it can compare by value, so the memo keys each state by the string `${n},${k}`; two arrays [n, k] would be two different keys.

Recorded with Node.js 24.21.0 LTS (V8 13.6) on macOS 26 arm64. It runs in your browser with QuickJS (quickjs-emscripten 0.32.0). To run it yourself: node main.mjs

Java 25 LTS · Main.java

import java.util.HashMap;
import java.util.List;
import java.util.Map;

public class Main {
  record Result(int value, int work) {}

  record State(int n, int k) {}

  /** C(n, k) by Pascal's rule, and how many calls it took. */
  static Result plain(int n, int k) {
    if (k == 0 || k == n) {
      return new Result(1, 1);
    }
    Result left = plain(n - 1, k - 1);
    Result right = plain(n - 1, k);
    return new Result(left.value() + right.value(), left.work() + right.work() + 1);
  }

  /** The same recursion with a memo of the states worked out. */
  static Result memo(int n, int k, Map<State, Integer> seen) {
    if (k == 0 || k == n) {
      return new Result(1, 1);
    }
    Integer known = seen.get(new State(n, k));
    if (known != null) {
      return new Result(known, 1);
    }
    Result left = memo(n - 1, k - 1, seen);
    Result right = memo(n - 1, k, seen);
    seen.put(new State(n, k), left.value() + right.value());
    return new Result(left.value() + right.value(), left.work() + right.work() + 1);
  }

  /** C(n, k) bottom-up in one row, counting its updates. */
  static Result table(int n, int k) {
    int[] row = new int[k + 1];
    row[0] = 1;
    int updates = 0;
    for (int i = 1; i <= n; i++) {
      // Right to left, so row[j - 1] still holds row i - 1 when row[j] reads it.
      for (int j = Math.min(i, k); j > 0; j--) {
        row[j] += row[j - 1];
        updates++;
      }
    }
    return new Result(row[k], updates);
  }

  public static void main(String[] args) {
    Result plain = plain(20, 10);
    System.out.println(
        "plain recursion: C(20, 10) = " + plain.value() + " after " + plain.work() + " calls");
    for (State state : List.of(new State(20, 10), new State(30, 15))) {
      String name = "C(" + state.n() + ", " + state.k() + ")";
      Map<State, Integer> seen = new HashMap<>();
      Result memo = memo(state.n(), state.k(), seen);
      System.out.println(
          "memo: "
              + name
              + " = "
              + memo.value()
              + " after "
              + memo.work()
              + " calls, "
              + seen.size()
              + " answers stored");
      Result table = table(state.n(), state.k());
      System.out.println(
          "one-row table: " + name + " = " + table.value() + " after " + table.work() + " updates");
    }
  }
}

In Java: The records Result and State compare by value, so a State(n, k) works as a HashMap key with no equals or hashCode written by hand.

Recorded with OpenJDK 25.0.4.1 LTS (Eclipse Temurin) on macOS 26 arm64. It runs in your browser with a TeaVM 0.16.0 build in QuickJS (quickjs-emscripten 0.32.0). To run it yourself: java Main.java

C++23 · main.cpp

#include <algorithm>
#include <map>
#include <print>
#include <utility>
#include <vector>

struct Result {
  int value, work;
};

// C(n, k) by Pascal's rule, and how many calls it took.
Result plain(int n, int k) {
  if (k == 0 || k == n)
    return {1, 1};
  const auto [left, left_calls] = plain(n - 1, k - 1);
  const auto [right, right_calls] = plain(n - 1, k);
  return {left + right, left_calls + right_calls + 1};
}

// The same recursion with a memo of the states worked out.
Result memo(int n, int k, std::map<std::pair<int, int>, int> &seen) {
  if (k == 0 || k == n)
    return {1, 1};
  if (const auto it = seen.find({n, k}); it != seen.end())
    return {it->second, 1};
  const auto [left, left_calls] = memo(n - 1, k - 1, seen);
  const auto [right, right_calls] = memo(n - 1, k, seen);
  seen[{n, k}] = left + right;
  return {left + right, left_calls + right_calls + 1};
}

// C(n, k) bottom-up in one row, counting its updates.
Result table(int n, int k) {
  std::vector<int> row(k + 1);
  row[0] = 1;
  int updates = 0;
  for (int i = 1; i <= n; ++i) {
    // Right to left, so row[j - 1] still holds row i - 1 when row[j] reads it.
    for (int j = std::min(i, k); j > 0; --j) {
      row[j] += row[j - 1];
      ++updates;
    }
  }
  return {row[k], updates};
}

int main() {
  const auto [value, calls] = plain(20, 10);
  std::println("plain recursion: C(20, 10) = {} after {} calls", value, calls);
  for (const auto &[n, k] : {std::pair{20, 10}, std::pair{30, 15}}) {
    std::map<std::pair<int, int>, int> seen;
    const auto [memo_value, memo_calls] = memo(n, k, seen);
    std::println("memo: C({}, {}) = {} after {} calls, {} answers stored", n, k,
                 memo_value, memo_calls, seen.size());
    const auto [table_value, updates] = table(n, k);
    std::println("one-row table: C({}, {}) = {} after {} updates", n, k,
                 table_value, updates);
  }
}

In C++: std::map keys the memo by std::pair<int, int>, because the standard library has no hash for pairs; find looks a state up without inserting it.

Recorded with Apple clang 21.0.0 (C++23) and GCC 16.2.0 on macOS 26 arm64. It runs in your browser with Clang in WebAssembly (YoWASP) 22.0.0-git20542-10. To run it yourself: clang++ -std=c++23 -O2 -Wall -Wextra -Werror -pedantic -fsanitize=address,undefined main.cpp -o main && ./main

C# 14 · .NET 10 · app.cs

using System.Globalization;

CultureInfo.CurrentCulture = CultureInfo.InvariantCulture;

var (value, calls) = Plain(20, 10);
Console.WriteLine($"plain recursion: C(20, 10) = {value} after {calls} calls");
foreach (var (n, k) in new[] { (20, 10), (30, 15) })
{
    var seen = new Dictionary<(int, int), int>();
    var (memoValue, memoCalls) = Memo(n, k, seen);
    Console.WriteLine(
        $"memo: C({n}, {k}) = {memoValue} after {memoCalls} calls, {seen.Count} answers stored");
    var (tableValue, updates) = Table(n, k);
    Console.WriteLine($"one-row table: C({n}, {k}) = {tableValue} after {updates} updates");
}

// C(n, k) by Pascal's rule, and how many calls it took.
static (int Value, int Calls) Plain(int n, int k)
{
    if (k == 0 || k == n)
    {
        return (1, 1);
    }
    var (left, leftCalls) = Plain(n - 1, k - 1);
    var (right, rightCalls) = Plain(n - 1, k);
    return (left + right, leftCalls + rightCalls + 1);
}

// The same recursion with a memo of the states worked out.
static (int Value, int Calls) Memo(int n, int k, Dictionary<(int, int), int> seen)
{
    if (k == 0 || k == n)
    {
        return (1, 1);
    }
    if (seen.TryGetValue((n, k), out int known))
    {
        return (known, 1);
    }
    var (left, leftCalls) = Memo(n - 1, k - 1, seen);
    var (right, rightCalls) = Memo(n - 1, k, seen);
    seen[(n, k)] = left + right;
    return (left + right, leftCalls + rightCalls + 1);
}

// C(n, k) bottom-up in one row, counting its updates.
static (int Value, int Updates) Table(int n, int k)
{
    var row = new int[k + 1];
    row[0] = 1;
    int updates = 0;
    for (int i = 1; i <= n; i++)
    {
        // Right to left, so row[j - 1] still holds row i - 1 when row[j] reads it.
        for (int j = Math.Min(i, k); j > 0; j--)
        {
            row[j] += row[j - 1];
            updates++;
        }
    }
    return (row[k], updates);
}

In C#: The tuple (int, int) is a value type with equality built in, so it works as a Dictionary key, and TryGetValue looks a state up and reads it at once.

Recorded with C# 14 on .NET 10.0.12 (SDK 10.0.401) on macOS 26 arm64. It runs in your browser with the .NET runtime for WebAssembly 10.0.12. To run it yourself: dotnet run app.cs

C23 · main.c

#include <stdio.h>

typedef struct {
  int value, work;
} result;

// C(n, k) by Pascal's rule, and how many calls it took.
static result plain(int n, int k) {
  if (k == 0 || k == n)
    return (result){1, 1};
  const result left = plain(n - 1, k - 1), right = plain(n - 1, k);
  return (result){left.value + right.value, left.work + right.work + 1};
}

// The same recursion with a memo of the states worked out.
static result memo(int n, int k, int seen[31][31], int *stored) {
  if (k == 0 || k == n)
    return (result){1, 1};
  if (seen[n][k] > 0)
    return (result){seen[n][k], 1};
  const result left = memo(n - 1, k - 1, seen, stored);
  const result right = memo(n - 1, k, seen, stored);
  seen[n][k] = left.value + right.value;
  ++*stored;
  return (result){seen[n][k], left.work + right.work + 1};
}

// C(n, k) bottom-up in one row, counting its updates.
static result table(int n, int k) {
  int row[31] = {1};
  int updates = 0;
  for (int i = 1; i <= n; i++) {
    // Right to left, so row[j - 1] still holds row i - 1 when row[j] reads it.
    for (int j = i < k ? i : k; j > 0; j--) {
      row[j] += row[j - 1];
      updates++;
    }
  }
  return (result){row[k], updates};
}

int main(void) {
  const result p = plain(20, 10);
  printf("plain recursion: C(20, 10) = %d after %d calls\n", p.value, p.work);
  const int cases[2][2] = {{20, 10}, {30, 15}};
  for (int c = 0; c < 2; c++) {
    const int n = cases[c][0], k = cases[c][1];
    int seen[31][31] = {{0}}, stored = 0;
    const result m = memo(n, k, seen, &stored);
    printf("memo: C(%d, %d) = %d after %d calls, %d answers stored\n", n, k,
           m.value, m.work, stored);
    const result t = table(n, k);
    printf("one-row table: C(%d, %d) = %d after %d updates\n", n, k, t.value,
           t.work);
  }
  return 0;
}

In C: C has no hash map, so the memo is a 31 × 31 array in which 0 means not worked out yet; every C(n, k) is at least 1, so 0 can safely mean that.

Recorded with Apple clang 21.0.0 (C23) and GCC 16.2.0 on macOS 26 arm64. It runs in your browser with Clang in WebAssembly (YoWASP) 22.0.0-git20542-10. To run it yourself: clang -std=c23 -O2 -Wall -Wextra -Werror -pedantic -fsanitize=address,undefined main.c -o main && ./main

PHP 8.5 · main.php

<?php

declare(strict_types=1);

/**
 * C(n, k) by Pascal's rule, and how many calls it took.
 *
 * @return array{int, int}
 */
function plain(int $n, int $k): array
{
    if ($k === 0 || $k === $n) {
        return [1, 1];
    }
    [$left, $leftCalls] = plain($n - 1, $k - 1);
    [$right, $rightCalls] = plain($n - 1, $k);
    return [$left + $right, $leftCalls + $rightCalls + 1];
}

/**
 * The same recursion with a memo of the states worked out.
 *
 * @param array<string, int> $seen
 * @return array{int, int}
 */
function memo(int $n, int $k, array &$seen): array
{
    if ($k === 0 || $k === $n) {
        return [1, 1];
    }
    if (isset($seen["$n,$k"])) {
        return [$seen["$n,$k"], 1];
    }
    [$left, $leftCalls] = memo($n - 1, $k - 1, $seen);
    [$right, $rightCalls] = memo($n - 1, $k, $seen);
    $seen["$n,$k"] = $left + $right;
    return [$left + $right, $leftCalls + $rightCalls + 1];
}

/**
 * C(n, k) bottom-up in one row, counting its updates.
 *
 * @return array{int, int}
 */
function table(int $n, int $k): array
{
    $row = array_fill(0, $k + 1, 0);
    $row[0] = 1;
    $updates = 0;
    for ($i = 1; $i <= $n; $i++) {
        // Right to left, so row[j - 1] still holds row i - 1 when row[j] reads it.
        for ($j = min($i, $k); $j > 0; $j--) {
            $row[$j] += $row[$j - 1];
            $updates++;
        }
    }
    return [$row[$k], $updates];
}

[$value, $calls] = plain(20, 10);
echo "plain recursion: C(20, 10) = {$value} after {$calls} calls\n";
foreach ([[20, 10], [30, 15]] as [$n, $k]) {
    $seen = [];
    [$value, $calls] = memo($n, $k, $seen);
    $stored = count($seen);
    echo "memo: C({$n}, {$k}) = {$value} after {$calls} calls, {$stored} answers stored\n";
    [$value, $updates] = table($n, $k);
    echo "one-row table: C({$n}, {$k}) = {$value} after {$updates} updates\n";
}

In PHP: The memo is an array keyed by the string "n,k" and passed by reference (&$seen), since PHP copies arrays passed by value.

Recorded with PHP 8.5.11 (CLI) on macOS 26 arm64. It runs in your browser with php-wasm 0.2.0 (PHP 8.5.2). To run it yourself: php main.php

Rust 1.99 · main.rs

use std::collections::HashMap;

/// C(n, k) by Pascal's rule, and how many calls it took.
fn plain(n: u32, k: u32) -> (u32, u32) {
    if k == 0 || k == n {
        return (1, 1);
    }
    let (left, left_calls) = plain(n - 1, k - 1);
    let (right, right_calls) = plain(n - 1, k);
    (left + right, left_calls + right_calls + 1)
}

/// The same recursion with a memo of the states worked out.
fn memo(n: u32, k: u32, seen: &mut HashMap<(u32, u32), u32>) -> (u32, u32) {
    if k == 0 || k == n {
        return (1, 1);
    }
    if let Some(&known) = seen.get(&(n, k)) {
        return (known, 1);
    }
    let (left, left_calls) = memo(n - 1, k - 1, seen);
    let (right, right_calls) = memo(n - 1, k, seen);
    seen.insert((n, k), left + right);
    (left + right, left_calls + right_calls + 1)
}

/// C(n, k) bottom-up in one row, counting its updates.
fn table(n: usize, k: usize) -> (u32, u32) {
    let mut row = vec![0; k + 1];
    row[0] = 1;
    let mut updates = 0;
    for i in 1..=n {
        // Right to left, so row[j - 1] still holds row i - 1 when row[j] reads it.
        for j in (1..=i.min(k)).rev() {
            row[j] += row[j - 1];
            updates += 1;
        }
    }
    (row[k], updates)
}

fn main() {
    let (value, calls) = plain(20, 10);
    println!("plain recursion: C(20, 10) = {value} after {calls} calls");
    for (n, k) in [(20, 10), (30, 15)] {
        let mut seen = HashMap::new();
        let (value, calls) = memo(n, k, &mut seen);
        let stored = seen.len();
        println!("memo: C({n}, {k}) = {value} after {calls} calls, {stored} answers stored");
        let (value, updates) = table(n as usize, k as usize);
        println!("one-row table: C({n}, {k}) = {value} after {updates} updates");
    }
}

In Rust: The memo is a HashMap<(u32, u32), u32> borrowed mutably by every call; if let Some(&known) looks a state up and copies its value out.

Recorded with rustc 1.99.0 (edition 2024) on macOS 26 arm64. It runs in your browser with a WebAssembly build on the WASI runner (browser_wasi_shim 0.4.2). To run it yourself: rustc --edition 2024 -O main.rs && ./main

TypeScript 6.0 · main.ts

type Result = [value: number, work: number];

// C(n, k) by Pascal's rule, and how many calls it took.
function plain(n: number, k: number): Result {
  if (k === 0 || k === n) return [1, 1];
  const [left, leftCalls] = plain(n - 1, k - 1);
  const [right, rightCalls] = plain(n - 1, k);
  return [left + right, leftCalls + rightCalls + 1];
}

// The same recursion with a memo of the states worked out.
function memo(n: number, k: number, seen: Map<string, number>): Result {
  if (k === 0 || k === n) return [1, 1];
  const key = `${n},${k}`;
  const known = seen.get(key);
  if (known !== undefined) return [known, 1];
  const [left, leftCalls] = memo(n - 1, k - 1, seen);
  const [right, rightCalls] = memo(n - 1, k, seen);
  seen.set(key, left + right);
  return [left + right, leftCalls + rightCalls + 1];
}

// C(n, k) bottom-up in one row, counting its updates.
function table(n: number, k: number): Result {
  const row: number[] = [1, ...new Array<number>(k).fill(0)];
  let updates = 0;
  for (let i = 1; i <= n; i++) {
    // Right to left, so row[j - 1] still holds row i - 1 when row[j] reads it.
    for (let j = Math.min(i, k); j > 0; j--) {
      row[j] += row[j - 1];
      updates++;
    }
  }
  return [row[k], updates];
}

const [value, calls] = plain(20, 10);
console.log(`plain recursion: C(20, 10) = ${value} after ${calls} calls`);
const cases: [number, number][] = [
  [20, 10],
  [30, 15],
];
for (const [n, k] of cases) {
  const seen = new Map<string, number>();
  const [memoValue, memoCalls] = memo(n, k, seen);
  console.log(
    `memo: C(${n}, ${k}) = ${memoValue} after ${memoCalls} calls, ${seen.size} answers stored`,
  );
  const [tableValue, updates] = table(n, k);
  console.log(`one-row table: C(${n}, ${k}) = ${tableValue} after ${updates} updates`);
}

In TypeScript: The named tuple type Result = [value, work] lets tsc check every return; the memo's get is tested against undefined instead of has then get.

Recorded with TypeScript 6.0.3 (strict), run by Node.js 24.21.0 on macOS 26 arm64. It runs in your browser with QuickJS (quickjs-emscripten 0.32.0) after Sucrase 3.35.1. To run it yourself: npx -p typescript@6.0.3 tsc --noEmit --strict main.ts && node main.ts

Go 1.27 · main.go

package main

import "fmt"

// plain computes C(n, k) by Pascal's rule and counts its calls.
func plain(n, k int) (value, calls int) {
	if k == 0 || k == n {
		return 1, 1
	}
	left, leftCalls := plain(n-1, k-1)
	right, rightCalls := plain(n-1, k)
	return left + right, leftCalls + rightCalls + 1
}

// memo is the same recursion with a memo of the states worked out.
func memo(n, k int, seen map[[2]int]int) (value, calls int) {
	if k == 0 || k == n {
		return 1, 1
	}
	if known, ok := seen[[2]int{n, k}]; ok {
		return known, 1
	}
	left, leftCalls := memo(n-1, k-1, seen)
	right, rightCalls := memo(n-1, k, seen)
	seen[[2]int{n, k}] = left + right
	return left + right, leftCalls + rightCalls + 1
}

// table computes C(n, k) bottom-up in one row, counting its updates.
func table(n, k int) (value, updates int) {
	row := make([]int, k+1)
	row[0] = 1
	for i := 1; i <= n; i++ {
		// Right to left, so row[j - 1] still holds row i - 1 when row[j] reads it.
		for j := min(i, k); j > 0; j-- {
			row[j] += row[j-1]
			updates++
		}
	}
	return row[k], updates
}

func main() {
	value, calls := plain(20, 10)
	fmt.Printf("plain recursion: C(20, 10) = %d after %d calls\n", value, calls)
	for _, c := range [][2]int{{20, 10}, {30, 15}} {
		n, k := c[0], c[1]
		seen := map[[2]int]int{}
		value, calls := memo(n, k, seen)
		fmt.Printf("memo: C(%d, %d) = %d after %d calls, %d answers stored\n",
			n, k, value, calls, len(seen))
		value, updates := table(n, k)
		fmt.Printf("one-row table: C(%d, %d) = %d after %d updates\n", n, k, value, updates)
	}
}

In Go: An array [2]int is comparable, so it works as a map key; the functions return two named results, the value and the work.

Recorded with Go 1.27.1 on macOS 26 arm64. It runs in your browser with the Go compiler in WebAssembly 1.27.1. To run it yourself: go run main.go

Swift 6.4 · main.swift

struct State: Hashable {
  let n: Int
  let k: Int
}

/// C(n, k) by Pascal's rule, and how many calls it took.
func plain(_ n: Int, _ k: Int) -> (value: Int, calls: Int) {
  if k == 0 || k == n { return (1, 1) }
  let left = plain(n - 1, k - 1)
  let right = plain(n - 1, k)
  return (left.value + right.value, left.calls + right.calls + 1)
}

/// The same recursion with a memo of the states worked out.
func memo(_ n: Int, _ k: Int, _ seen: inout [State: Int]) -> (value: Int, calls: Int) {
  if k == 0 || k == n { return (1, 1) }
  if let known = seen[State(n: n, k: k)] { return (known, 1) }
  let left = memo(n - 1, k - 1, &seen)
  let right = memo(n - 1, k, &seen)
  seen[State(n: n, k: k)] = left.value + right.value
  return (left.value + right.value, left.calls + right.calls + 1)
}

/// C(n, k) bottom-up in one row, counting its updates.
func table(_ n: Int, _ k: Int) -> (value: Int, updates: Int) {
  var row = [1] + Array(repeating: 0, count: k)
  var updates = 0
  for i in stride(from: 1, through: n, by: 1) {
    // Right to left, so row[j - 1] still holds row i - 1 when row[j] reads it.
    for j in stride(from: min(i, k), to: 0, by: -1) {
      row[j] += row[j - 1]
      updates += 1
    }
  }
  return (row[k], updates)
}

let first = plain(20, 10)
print("plain recursion: C(20, 10) = \(first.value) after \(first.calls) calls")
for (n, k) in [(20, 10), (30, 15)] {
  var seen: [State: Int] = [:]
  let m = memo(n, k, &seen)
  print("memo: C(\(n), \(k)) = \(m.value) after \(m.calls) calls, \(seen.count) answers stored")
  let t = table(n, k)
  print("one-row table: C(\(n), \(k)) = \(t.value) after \(t.updates) updates")
}

In Swift: A small Hashable struct State keys the dictionary, and the memo is passed inout so that every call adds to the same one.

Recorded with Apple Swift 6.4 on macOS 26 arm64. It runs in your browser with a WebAssembly build on the WASI runner (browser_wasi_shim 0.4.2). To run it yourself: swiftc -O main.swift -o main && ./main

Ruby 4.0 · main.rb

# frozen_string_literal: true

# C(n, k) by Pascal's rule, and how many calls it took.
def plain(count, choose)
  return [1, 1] if choose.zero? || choose == count

  left, left_calls = plain(count - 1, choose - 1)
  right, right_calls = plain(count - 1, choose)
  [left + right, left_calls + right_calls + 1]
end

# The same recursion with a memo of the states worked out.
def memo(count, choose, seen)
  return [1, 1] if choose.zero? || choose == count
  return [seen[[count, choose]], 1] if seen.key?([count, choose])

  left, left_calls = memo(count - 1, choose - 1, seen)
  right, right_calls = memo(count - 1, choose, seen)
  seen[[count, choose]] = left + right
  [left + right, left_calls + right_calls + 1]
end

# C(n, k) bottom-up in one row, counting its updates.
def table(count, choose)
  row = [1] + Array.new(choose, 0)
  updates = 0
  1.upto(count) do |i|
    # Right to left, so row[j - 1] still holds row i - 1 when row[j] reads it.
    [i, choose].min.downto(1) do |j|
      row[j] += row[j - 1]
      updates += 1
    end
  end
  [row[choose], updates]
end

value, calls = plain(20, 10)
puts "plain recursion: C(20, 10) = #{value} after #{calls} calls"
[[20, 10], [30, 15]].each do |count, choose|
  seen = {}
  value, calls = memo(count, choose, seen)
  puts "memo: C(#{count}, #{choose}) = #{value} after #{calls} calls, #{seen.size} answers stored"
  value, updates = table(count, choose)
  puts "one-row table: C(#{count}, #{choose}) = #{value} after #{updates} updates"
end

In Ruby: Arrays compare by value, so [count, choose] works as a hash key; the parameters are named count and choose, as RuboCop asks for names of three letters or more.

Recorded with CRuby 4.0.7 on macOS 26 arm64. It runs in your browser with ruby.wasm 2.10.1 (Ruby 4.0.0). To run it yourself: ruby main.rb

Kotlin 2.4 · Main.kt

// C(n, k) by Pascal's rule, and how many calls it took.
fun plain(
    n: Int,
    k: Int,
): Pair<Int, Int> {
    if (k == 0 || k == n) return 1 to 1
    val (left, leftCalls) = plain(n - 1, k - 1)
    val (right, rightCalls) = plain(n - 1, k)
    return left + right to leftCalls + rightCalls + 1
}

// The same recursion with a memo of the states worked out.
fun memo(
    n: Int,
    k: Int,
    seen: MutableMap<Pair<Int, Int>, Int>,
): Pair<Int, Int> {
    if (k == 0 || k == n) return 1 to 1
    seen[n to k]?.let { return it to 1 }
    val (left, leftCalls) = memo(n - 1, k - 1, seen)
    val (right, rightCalls) = memo(n - 1, k, seen)
    seen[n to k] = left + right
    return left + right to leftCalls + rightCalls + 1
}

// C(n, k) bottom-up in one row, counting its updates.
fun table(
    n: Int,
    k: Int,
): Pair<Int, Int> {
    val row = IntArray(k + 1)
    row[0] = 1
    var updates = 0
    for (i in 1..n) {
        // Right to left, so row[j - 1] still holds row i - 1 when row[j] reads it.
        for (j in minOf(i, k) downTo 1) {
            row[j] += row[j - 1]
            updates++
        }
    }
    return row[k] to updates
}

fun main() {
    val (value, calls) = plain(20, 10)
    println("plain recursion: C(20, 10) = $value after $calls calls")
    for ((n, k) in listOf(20 to 10, 30 to 15)) {
        val seen = mutableMapOf<Pair<Int, Int>, Int>()
        val (memoValue, memoCalls) = memo(n, k, seen)
        println("memo: C($n, $k) = $memoValue after $memoCalls calls, ${seen.size} answers stored")
        val (tableValue, updates) = table(n, k)
        println("one-row table: C($n, $k) = $tableValue after $updates updates")
    }
}

In Kotlin: Pair<Int, Int> has value equality, so it keys the MutableMap, and seen[n to k]?.let returns early with a stored answer.

Recorded with Kotlin 2.4.20 on Java 25.0.4.1 on macOS 26 arm64. It runs in your browser with a WebAssembly build on the WASI runner (browser_wasi_shim 0.4.2). To run it yourself: kotlinc Main.kt -include-runtime -d main.jar && java -jar main.jar

Dart 3.13 · main.dart

// C(n, k) by Pascal's rule, and how many calls it took.
(int, int) plain(int n, int k) {
  if (k == 0 || k == n) return (1, 1);
  final (left, leftCalls) = plain(n - 1, k - 1);
  final (right, rightCalls) = plain(n - 1, k);
  return (left + right, leftCalls + rightCalls + 1);
}

// The same recursion with a memo of the states worked out.
(int, int) memo(int n, int k, Map<(int, int), int> seen) {
  if (k == 0 || k == n) return (1, 1);
  final known = seen[(n, k)];
  if (known != null) return (known, 1);
  final (left, leftCalls) = memo(n - 1, k - 1, seen);
  final (right, rightCalls) = memo(n - 1, k, seen);
  seen[(n, k)] = left + right;
  return (left + right, leftCalls + rightCalls + 1);
}

// C(n, k) bottom-up in one row, counting its updates.
(int, int) table(int n, int k) {
  final row = List.filled(k + 1, 0)..[0] = 1;
  var updates = 0;
  for (var i = 1; i <= n; i++) {
    // Right to left, so row[j - 1] still holds row i - 1 when row[j] reads it.
    for (var j = i < k ? i : k; j > 0; j--) {
      row[j] += row[j - 1];
      updates++;
    }
  }
  return (row[k], updates);
}

void main() {
  final (value, calls) = plain(20, 10);
  print('plain recursion: C(20, 10) = $value after $calls calls');
  for (final (n, k) in [(20, 10), (30, 15)]) {
    final seen = <(int, int), int>{};
    final (memoValue, memoCalls) = memo(n, k, seen);
    print(
      'memo: C($n, $k) = $memoValue after $memoCalls calls, ${seen.length} answers stored',
    );
    final (tableValue, updates) = table(n, k);
    print('one-row table: C($n, $k) = $tableValue after $updates updates');
  }
}

In Dart: Records have value equality, so (n, k) keys the Map directly, and the functions return (int, int) records.

Recorded with Dart 3.13.5 on macOS 26 arm64. It runs in your browser with a WebAssembly build by dart2wasm 3.13.5. To run it yourself: dart run main.dart

Python 3.14 · main.py

TRIANGLE = [[5], [9, 6], [4, 6, 8], [0, 7, 1, 20]]


def every_path(tri: list[list[int]]) -> int:
    """The heaviest path, by trying all 2^(rows - 1) of them."""
    heaviest = 0
    for moves in range(2 ** (len(tri) - 1)):
        col, total = 0, tri[0][0]
        for row in range(1, len(tri)):
            col += (moves >> (row - 1)) & 1  # bit row - 1 set: step down and right
            total += tri[row][col]
        heaviest = max(heaviest, total)
    return heaviest


def greedy(tri: list[list[int]]) -> int:
    """Always step to the larger of the two numbers below."""
    col, total = 0, tri[0][0]
    for row in range(1, len(tri)):
        if tri[row][col + 1] > tri[row][col]:
            col += 1
        total += tri[row][col]
    return total


def table(tri: list[list[int]]) -> int:
    """best[c] is the heaviest path from cell c of a row to the bottom, filled bottom-up."""
    best = tri[-1]
    print(f"row {len(tri) - 1}: {' '.join(map(str, best))}")
    for row in range(len(tri) - 2, -1, -1):
        best = [tri[row][c] + max(best[c], best[c + 1]) for c in range(row + 1)]
        print(f"row {row}: {' '.join(map(str, best))}")
    return best[0]


print(f"every path: {every_path(TRIANGLE)} after {2 ** (len(TRIANGLE) - 1)} paths")
print(f"greedy walk: {greedy(TRIANGLE)}")
print(f"table: {table(TRIANGLE)}")

In Python: Bit row − 1 of moves says whether the path steps down and to the right at that row, so the numbers 0 to 7 name all 8 paths.

Recorded with CPython 3.14.8 on macOS 26 arm64. It runs in your browser with Pyodide 314.0.7 (CPython 3.14.2). To run it yourself: python3 main.py

JavaScript Node 24 · main.mjs

const TRIANGLE = [[5], [9, 6], [4, 6, 8], [0, 7, 1, 20]];

// The heaviest path, by trying all 2^(rows - 1) of them.
function everyPath(tri) {
  let heaviest = 0;
  for (let moves = 0; moves < 2 ** (tri.length - 1); moves++) {
    let col = 0;
    let total = tri[0][0];
    for (let row = 1; row < tri.length; row++) {
      col += (moves >> (row - 1)) & 1; // bit row - 1 set: step down and right
      total += tri[row][col];
    }
    heaviest = Math.max(heaviest, total);
  }
  return heaviest;
}

// Always step to the larger of the two numbers below.
function greedy(tri) {
  let col = 0;
  let total = tri[0][0];
  for (let row = 1; row < tri.length; row++) {
    if (tri[row][col + 1] > tri[row][col]) col++;
    total += tri[row][col];
  }
  return total;
}

// best[c] is the heaviest path from cell c of a row to the bottom, filled bottom-up.
function table(tri) {
  let best = tri.at(-1);
  console.log(`row ${tri.length - 1}: ${best.join(" ")}`);
  for (let row = tri.length - 2; row >= 0; row--) {
    best = tri[row].map((cell, c) => cell + Math.max(best[c], best[c + 1]));
    console.log(`row ${row}: ${best.join(" ")}`);
  }
  return best[0];
}

console.log(`every path: ${everyPath(TRIANGLE)} after ${2 ** (TRIANGLE.length - 1)} paths`);
console.log(`greedy walk: ${greedy(TRIANGLE)}`);
console.log(`table: ${table(TRIANGLE)}`);

In JavaScript: tri.at(-1) reads the last row; each new row of best is a map over the cells above, so best is never updated in place.

Recorded with Node.js 24.21.0 LTS (V8 13.6) on macOS 26 arm64. It runs in your browser with QuickJS (quickjs-emscripten 0.32.0). To run it yourself: node main.mjs

Java 25 LTS · Main.java

public class Main {
  static final int[][] TRIANGLE = {{5}, {9, 6}, {4, 6, 8}, {0, 7, 1, 20}};

  /** The heaviest path, by trying all 2^(rows - 1) of them. */
  static int everyPath(int[][] tri) {
    int heaviest = 0;
    for (int moves = 0; moves < 1 << (tri.length - 1); moves++) {
      int col = 0;
      int total = tri[0][0];
      for (int row = 1; row < tri.length; row++) {
        col += (moves >> (row - 1)) & 1; // bit row - 1 set: step down and right
        total += tri[row][col];
      }
      heaviest = Math.max(heaviest, total);
    }
    return heaviest;
  }

  /** Always step to the larger of the two numbers below. */
  static int greedy(int[][] tri) {
    int col = 0;
    int total = tri[0][0];
    for (int row = 1; row < tri.length; row++) {
      if (tri[row][col + 1] > tri[row][col]) {
        col++;
      }
      total += tri[row][col];
    }
    return total;
  }

  /** best[c] is the heaviest path from cell c of a row to the bottom, filled bottom-up. */
  static int table(int[][] tri) {
    int[] best = tri[tri.length - 1];
    System.out.println("row " + (tri.length - 1) + ": " + joined(best));
    for (int row = tri.length - 2; row >= 0; row--) {
      int[] above = new int[row + 1];
      for (int c = 0; c <= row; c++) {
        above[c] = tri[row][c] + Math.max(best[c], best[c + 1]);
      }
      best = above;
      System.out.println("row " + row + ": " + joined(best));
    }
    return best[0];
  }

  static String joined(int[] values) {
    var out = new StringBuilder();
    for (int value : values) {
      if (out.length() > 0) {
        out.append(' ');
      }
      out.append(value);
    }
    return out.toString();
  }

  public static void main(String[] args) {
    int paths = 1 << (TRIANGLE.length - 1);
    System.out.println("every path: " + everyPath(TRIANGLE) + " after " + paths + " paths");
    System.out.println("greedy walk: " + greedy(TRIANGLE));
    System.out.println("table: " + table(TRIANGLE));
  }
}

In Java: The rows are int arrays of different lengths, a jagged array, and a small joined helper prints each row of the table.

Recorded with OpenJDK 25.0.4.1 LTS (Eclipse Temurin) on macOS 26 arm64. It runs in your browser with a TeaVM 0.16.0 build in QuickJS (quickjs-emscripten 0.32.0). To run it yourself: java Main.java

C++23 · main.cpp

#include <algorithm>
#include <print>
#include <vector>

using Triangle = std::vector<std::vector<int>>;

const Triangle TRIANGLE = {{5}, {9, 6}, {4, 6, 8}, {0, 7, 1, 20}};

// The heaviest path, by trying all 2^(rows - 1) of them.
int every_path(const Triangle &tri) {
  const int rows = static_cast<int>(tri.size());
  int heaviest = 0;
  for (int moves = 0; moves < 1 << (rows - 1); ++moves) {
    int col = 0, total = tri[0][0];
    for (int row = 1; row < rows; ++row) {
      col += (moves >> (row - 1)) & 1; // bit row - 1 set: step down and right
      total += tri[row][col];
    }
    heaviest = std::max(heaviest, total);
  }
  return heaviest;
}

// Always step to the larger of the two numbers below.
int greedy(const Triangle &tri) {
  int col = 0, total = tri[0][0];
  for (std::size_t row = 1; row < tri.size(); ++row) {
    if (tri[row][col + 1] > tri[row][col])
      ++col;
    total += tri[row][col];
  }
  return total;
}

void show(std::size_t row, const std::vector<int> &best) {
  std::print("row {}:", row);
  for (const int value : best)
    std::print(" {}", value);
  std::println("");
}

// best[c] is the heaviest path from cell c of a row to the bottom, filled
// bottom-up.
int table(const Triangle &tri) {
  std::vector<int> best = tri.back();
  show(tri.size() - 1, best);
  for (int row = static_cast<int>(tri.size()) - 2; row >= 0; --row) {
    std::vector<int> above(row + 1);
    for (int c = 0; c <= row; ++c)
      above[c] = tri[row][c] + std::max(best[c], best[c + 1]);
    best = above;
    show(row, best);
  }
  return best[0];
}

int main() {
  std::println("every path: {} after {} paths", every_path(TRIANGLE),
               1 << (TRIANGLE.size() - 1));
  std::println("greedy walk: {}", greedy(TRIANGLE));
  std::println("table: {}", table(TRIANGLE));
}

In C++: std::println would print a vector with brackets and commas, so show prints the numbers of a row one by one.

Recorded with Apple clang 21.0.0 (C++23) and GCC 16.2.0 on macOS 26 arm64. It runs in your browser with Clang in WebAssembly (YoWASP) 22.0.0-git20542-10. To run it yourself: clang++ -std=c++23 -O2 -Wall -Wextra -Werror -pedantic -fsanitize=address,undefined main.cpp -o main && ./main

C# 14 · .NET 10 · app.cs

int[][] triangle = [[5], [9, 6], [4, 6, 8], [0, 7, 1, 20]];

Console.WriteLine($"every path: {EveryPath(triangle)} after {1 << (triangle.Length - 1)} paths");
Console.WriteLine($"greedy walk: {Greedy(triangle)}");
Console.WriteLine($"table: {Table(triangle)}");

// The heaviest path, by trying all 2^(rows - 1) of them.
static int EveryPath(int[][] tri)
{
    int heaviest = 0;
    for (int moves = 0; moves < 1 << (tri.Length - 1); moves++)
    {
        int col = 0, total = tri[0][0];
        for (int row = 1; row < tri.Length; row++)
        {
            col += (moves >> (row - 1)) & 1; // bit row - 1 set: step down and right
            total += tri[row][col];
        }
        heaviest = Math.Max(heaviest, total);
    }
    return heaviest;
}

// Always step to the larger of the two numbers below.
static int Greedy(int[][] tri)
{
    int col = 0, total = tri[0][0];
    for (int row = 1; row < tri.Length; row++)
    {
        if (tri[row][col + 1] > tri[row][col])
        {
            col++;
        }
        total += tri[row][col];
    }
    return total;
}

// best[c] is the heaviest path from cell c of a row to the bottom, filled bottom-up.
static int Table(int[][] tri)
{
    int[] best = tri[^1];
    Console.WriteLine($"row {tri.Length - 1}: {string.Join(" ", best)}");
    for (int row = tri.Length - 2; row >= 0; row--)
    {
        best = tri[row].Select((cell, c) => cell + Math.Max(best[c], best[c + 1])).ToArray();
        Console.WriteLine($"row {row}: {string.Join(" ", best)}");
    }
    return best[0];
}

In C#: tri[^1] is the last row, and Select((cell, c) => …) gives each cell with its index, the same map the other languages use.

Recorded with C# 14 on .NET 10.0.12 (SDK 10.0.401) on macOS 26 arm64. It runs in your browser with the .NET runtime for WebAssembly 10.0.12. To run it yourself: dotnet run app.cs

C23 · main.c

#include <stdio.h>

enum { ROWS = 4 };

static const int TRIANGLE[ROWS][ROWS] = {{5}, {9, 6}, {4, 6, 8}, {0, 7, 1, 20}};

static int max(int a, int b) { return a > b ? a : b; }

// The heaviest path, by trying all 2^(rows - 1) of them.
static int every_path(void) {
  int heaviest = 0;
  for (int moves = 0; moves < 1 << (ROWS - 1); moves++) {
    int col = 0, total = TRIANGLE[0][0];
    for (int row = 1; row < ROWS; row++) {
      col += (moves >> (row - 1)) & 1; // bit row - 1 set: step down and right
      total += TRIANGLE[row][col];
    }
    heaviest = max(heaviest, total);
  }
  return heaviest;
}

// Always step to the larger of the two numbers below.
static int greedy(void) {
  int col = 0, total = TRIANGLE[0][0];
  for (int row = 1; row < ROWS; row++) {
    if (TRIANGLE[row][col + 1] > TRIANGLE[row][col])
      col++;
    total += TRIANGLE[row][col];
  }
  return total;
}

static void show(int row, const int *best) {
  printf("row %d:", row);
  for (int c = 0; c <= row; c++)
    printf(" %d", best[c]);
  printf("\n");
}

// best[c] is the heaviest path from cell c of a row to the bottom, filled
// bottom-up.
static int table(void) {
  int best[ROWS];
  for (int c = 0; c < ROWS; c++)
    best[c] = TRIANGLE[ROWS - 1][c];
  show(ROWS - 1, best);
  for (int row = ROWS - 2; row >= 0; row--) {
    for (int c = 0; c <= row; c++)
      best[c] = TRIANGLE[row][c] + max(best[c], best[c + 1]);
    show(row, best);
  }
  return best[0];
}

int main(void) {
  printf("every path: %d after %d paths\n", every_path(), 1 << (ROWS - 1));
  printf("greedy walk: %d\n", greedy());
  printf("table: %d\n", table());
  return 0;
}

In C: The rows are padded to four numbers in a 4 × 4 array, and best is updated in place from left to right, which is safe because cell c reads only cells c and c + 1 of the row below.

Recorded with Apple clang 21.0.0 (C23) and GCC 16.2.0 on macOS 26 arm64. It runs in your browser with Clang in WebAssembly (YoWASP) 22.0.0-git20542-10. To run it yourself: clang -std=c23 -O2 -Wall -Wextra -Werror -pedantic -fsanitize=address,undefined main.c -o main && ./main

PHP 8.5 · main.php

<?php

declare(strict_types=1);

const TRIANGLE = [[5], [9, 6], [4, 6, 8], [0, 7, 1, 20]];

/**
 * The heaviest path, by trying all 2^(rows - 1) of them.
 *
 * @param list<list<int>> $tri
 */
function everyPath(array $tri): int
{
    $heaviest = 0;
    for ($moves = 0; $moves < 1 << (count($tri) - 1); $moves++) {
        [$col, $total] = [0, $tri[0][0]];
        for ($row = 1; $row < count($tri); $row++) {
            $col += ($moves >> ($row - 1)) & 1; // bit row - 1 set: step down and right
            $total += $tri[$row][$col];
        }
        $heaviest = max($heaviest, $total);
    }
    return $heaviest;
}

/**
 * Always step to the larger of the two numbers below.
 *
 * @param list<list<int>> $tri
 */
function greedy(array $tri): int
{
    [$col, $total] = [0, $tri[0][0]];
    for ($row = 1; $row < count($tri); $row++) {
        if ($tri[$row][$col + 1] > $tri[$row][$col]) {
            $col++;
        }
        $total += $tri[$row][$col];
    }
    return $total;
}

/**
 * best[c] is the heaviest path from cell c of a row to the bottom, filled bottom-up.
 *
 * @param list<list<int>> $tri
 */
function table(array $tri): int
{
    $best = $tri[count($tri) - 1];
    echo 'row ' . (count($tri) - 1) . ': ' . implode(' ', $best) . "\n";
    for ($row = count($tri) - 2; $row >= 0; $row--) {
        $best = array_map(
            fn(int $c): int => $tri[$row][$c] + max($best[$c], $best[$c + 1]),
            range(0, $row),
        );
        echo "row {$row}: " . implode(' ', $best) . "\n";
    }
    return $best[0];
}

$paths = 1 << (count(TRIANGLE) - 1);
echo 'every path: ' . everyPath(TRIANGLE) . " after {$paths} paths\n";
echo 'greedy walk: ' . greedy(TRIANGLE) . "\n";
echo 'table: ' . table(TRIANGLE) . "\n";

In PHP: array_map over range(0, $row) builds each new row; the arrow function sees $tri, $row and $best without a use clause.

Recorded with PHP 8.5.11 (CLI) on macOS 26 arm64. It runs in your browser with php-wasm 0.2.0 (PHP 8.5.2). To run it yourself: php main.php

Rust 1.99 · main.rs

const TRIANGLE: [&[u32]; 4] = [&[5], &[9, 6], &[4, 6, 8], &[0, 7, 1, 20]];

/// The heaviest path, by trying all 2^(rows - 1) of them.
fn every_path(tri: &[&[u32]]) -> u32 {
    let mut heaviest = 0;
    for moves in 0..1u32 << (tri.len() - 1) {
        let (mut col, mut total) = (0, tri[0][0]);
        for row in 1..tri.len() {
            col += ((moves >> (row - 1)) & 1) as usize; // bit row - 1 set: step down and right
            total += tri[row][col];
        }
        heaviest = heaviest.max(total);
    }
    heaviest
}

/// Always step to the larger of the two numbers below.
fn greedy(tri: &[&[u32]]) -> u32 {
    let (mut col, mut total) = (0, tri[0][0]);
    for row in &tri[1..] {
        if row[col + 1] > row[col] {
            col += 1;
        }
        total += row[col];
    }
    total
}

fn joined(values: &[u32]) -> String {
    values
        .iter()
        .map(u32::to_string)
        .collect::<Vec<_>>()
        .join(" ")
}

/// best[c] is the heaviest path from cell c of a row to the bottom, filled bottom-up.
fn table(tri: &[&[u32]]) -> u32 {
    let mut best = tri[tri.len() - 1].to_vec();
    println!("row {}: {}", tri.len() - 1, joined(&best));
    for row in (0..tri.len() - 1).rev() {
        best = (0..=row)
            .map(|c| tri[row][c] + best[c].max(best[c + 1]))
            .collect();
        println!("row {row}: {}", joined(&best));
    }
    best[0]
}

fn main() {
    let paths = 1 << (TRIANGLE.len() - 1);
    println!("every path: {} after {paths} paths", every_path(&TRIANGLE));
    println!("greedy walk: {}", greedy(&TRIANGLE));
    println!("table: {}", table(&TRIANGLE));
}

In Rust: The rows are slices of different lengths, &[u32], and each new row of best is collected from a map over the cells above.

Recorded with rustc 1.99.0 (edition 2024) on macOS 26 arm64. It runs in your browser with a WebAssembly build on the WASI runner (browser_wasi_shim 0.4.2). To run it yourself: rustc --edition 2024 -O main.rs && ./main

TypeScript 6.0 · main.ts

const TRIANGLE: number[][] = [[5], [9, 6], [4, 6, 8], [0, 7, 1, 20]];

// The heaviest path, by trying all 2^(rows - 1) of them.
function everyPath(tri: number[][]): number {
  let heaviest = 0;
  for (let moves = 0; moves < 2 ** (tri.length - 1); moves++) {
    let col = 0;
    let total = tri[0][0];
    for (let row = 1; row < tri.length; row++) {
      col += (moves >> (row - 1)) & 1; // bit row - 1 set: step down and right
      total += tri[row][col];
    }
    heaviest = Math.max(heaviest, total);
  }
  return heaviest;
}

// Always step to the larger of the two numbers below.
function greedy(tri: number[][]): number {
  let col = 0;
  let total = tri[0][0];
  for (let row = 1; row < tri.length; row++) {
    if (tri[row][col + 1] > tri[row][col]) col++;
    total += tri[row][col];
  }
  return total;
}

// best[c] is the heaviest path from cell c of a row to the bottom, filled bottom-up.
function table(tri: number[][]): number {
  let best = tri[tri.length - 1];
  console.log(`row ${tri.length - 1}: ${best.join(" ")}`);
  for (let row = tri.length - 2; row >= 0; row--) {
    best = tri[row].map((cell, c) => cell + Math.max(best[c], best[c + 1]));
    console.log(`row ${row}: ${best.join(" ")}`);
  }
  return best[0];
}

console.log(`every path: ${everyPath(TRIANGLE)} after ${2 ** (TRIANGLE.length - 1)} paths`);
console.log(`greedy walk: ${greedy(TRIANGLE)}`);
console.log(`table: ${table(TRIANGLE)}`);

In TypeScript: The triangle is typed number[][], and tri[tri.length - 1] stands in for tri.at(-1), whose type would include undefined.

Recorded with TypeScript 6.0.3 (strict), run by Node.js 24.21.0 on macOS 26 arm64. It runs in your browser with QuickJS (quickjs-emscripten 0.32.0) after Sucrase 3.35.1. To run it yourself: npx -p typescript@6.0.3 tsc --noEmit --strict main.ts && node main.ts

Go 1.27 · main.go

package main

import (
	"fmt"
	"strings"
)

var triangle = [][]int{{5}, {9, 6}, {4, 6, 8}, {0, 7, 1, 20}}

// everyPath finds the heaviest path by trying all 2^(rows - 1) of them.
func everyPath(tri [][]int) int {
	heaviest := 0
	for moves := 0; moves < 1<<(len(tri)-1); moves++ {
		col, total := 0, tri[0][0]
		for row := 1; row < len(tri); row++ {
			col += (moves >> (row - 1)) & 1 // bit row - 1 set: step down and right
			total += tri[row][col]
		}
		heaviest = max(heaviest, total)
	}
	return heaviest
}

// greedy always steps to the larger of the two numbers below.
func greedy(tri [][]int) int {
	col, total := 0, tri[0][0]
	for _, row := range tri[1:] {
		if row[col+1] > row[col] {
			col++
		}
		total += row[col]
	}
	return total
}

func joined(values []int) string {
	return strings.Trim(fmt.Sprint(values), "[]")
}

// table fills best[c], the heaviest path from cell c of a row to the bottom, bottom-up.
func table(tri [][]int) int {
	best := tri[len(tri)-1]
	fmt.Printf("row %d: %s\n", len(tri)-1, joined(best))
	for row := len(tri) - 2; row >= 0; row-- {
		above := make([]int, row+1)
		for c := range above {
			above[c] = tri[row][c] + max(best[c], best[c+1])
		}
		best = above
		fmt.Printf("row %d: %s\n", row, joined(best))
	}
	return best[0]
}

func main() {
	fmt.Printf("every path: %d after %d paths\n", everyPath(triangle), 1<<(len(triangle)-1))
	fmt.Printf("greedy walk: %d\n", greedy(triangle))
	fmt.Printf("table: %d\n", table(triangle))
}

In Go: fmt.Sprint prints a slice as [11 13 28], so joined trims the brackets to print the row.

Recorded with Go 1.27.1 on macOS 26 arm64. It runs in your browser with the Go compiler in WebAssembly 1.27.1. To run it yourself: go run main.go

Swift 6.4 · main.swift

let triangle = [[5], [9, 6], [4, 6, 8], [0, 7, 1, 20]]

/// The heaviest path, by trying all 2^(rows - 1) of them.
func everyPath(_ tri: [[Int]]) -> Int {
  var heaviest = 0
  for moves in 0..<(1 << (tri.count - 1)) {
    var (col, total) = (0, tri[0][0])
    for row in 1..<tri.count {
      col += (moves >> (row - 1)) & 1  // bit row - 1 set: step down and right
      total += tri[row][col]
    }
    heaviest = max(heaviest, total)
  }
  return heaviest
}

/// Always step to the larger of the two numbers below.
func greedy(_ tri: [[Int]]) -> Int {
  var (col, total) = (0, tri[0][0])
  for row in tri.dropFirst() {
    if row[col + 1] > row[col] { col += 1 }
    total += row[col]
  }
  return total
}

/// best[c] is the heaviest path from cell c of a row to the bottom, filled bottom-up.
func table(_ tri: [[Int]]) -> Int {
  var best = tri[tri.count - 1]
  print("row \(tri.count - 1): \(best.map(String.init).joined(separator: " "))")
  for row in stride(from: tri.count - 2, through: 0, by: -1) {
    best = (0...row).map { c in tri[row][c] + max(best[c], best[c + 1]) }
    print("row \(row): \(best.map(String.init).joined(separator: " "))")
  }
  return best[0]
}

print("every path: \(everyPath(triangle)) after \(1 << (triangle.count - 1)) paths")
print("greedy walk: \(greedy(triangle))")
print("table: \(table(triangle))")

In Swift: tri.dropFirst() walks the rows below the top one, and stride counts the rows back up to 0.

Recorded with Apple Swift 6.4 on macOS 26 arm64. It runs in your browser with a WebAssembly build on the WASI runner (browser_wasi_shim 0.4.2). To run it yourself: swiftc -O main.swift -o main && ./main

Ruby 4.0 · main.rb

# frozen_string_literal: true

TRIANGLE = [[5], [9, 6], [4, 6, 8], [0, 7, 1, 20]].freeze

# The heaviest path, by trying all 2^(rows - 1) of them.
def every_path(tri)
  (0...(1 << (tri.size - 1))).map { |moves| path_weight(tri, moves) }.max
end

def path_weight(tri, moves)
  col = 0
  total = tri[0][0]
  (1...tri.size).each do |row|
    col += (moves >> (row - 1)) & 1 # bit row - 1 set: step down and right
    total += tri[row][col]
  end
  total
end

# Always step to the larger of the two numbers below.
def greedy(tri)
  col = 0
  total = tri[0][0]
  tri.drop(1).each do |row|
    col += 1 if row[col + 1] > row[col]
    total += row[col]
  end
  total
end

def show(row, best) = puts("row #{row}: #{best.join(' ')}")
def above(cells, below) = cells.each_with_index.map { |cell, c| cell + below[c, 2].max }

# best[c] is the heaviest path from cell c of a row to the bottom, filled bottom-up.
def table(tri)
  best = tri.last
  show(tri.size - 1, best)
  (tri.size - 2).downto(0) do |row|
    best = above(tri[row], best)
    show(row, best)
  end
  best.first
end

puts "every path: #{every_path(TRIANGLE)} after #{1 << (TRIANGLE.size - 1)} paths"
puts "greedy walk: #{greedy(TRIANGLE)}"
puts "table: #{table(TRIANGLE)}"

In Ruby: The path's weight is a method of its own, path_weight, so that each method stays as short as RuboCop asks.

Recorded with CRuby 4.0.7 on macOS 26 arm64. It runs in your browser with ruby.wasm 2.10.1 (Ruby 4.0.0). To run it yourself: ruby main.rb

Kotlin 2.4 · Main.kt

val triangle = listOf(listOf(5), listOf(9, 6), listOf(4, 6, 8), listOf(0, 7, 1, 20))

// The heaviest path, by trying all 2^(rows - 1) of them.
fun everyPath(tri: List<List<Int>>): Int {
    var heaviest = 0
    for (moves in 0 until (1 shl (tri.size - 1))) {
        var col = 0
        var total = tri[0][0]
        for (row in 1 until tri.size) {
            col += (moves shr (row - 1)) and 1 // bit row - 1 set: step down and right
            total += tri[row][col]
        }
        heaviest = maxOf(heaviest, total)
    }
    return heaviest
}

// Always step to the larger of the two numbers below.
fun greedy(tri: List<List<Int>>): Int {
    var col = 0
    var total = tri[0][0]
    for (row in tri.drop(1)) {
        if (row[col + 1] > row[col]) col++
        total += row[col]
    }
    return total
}

// best[c] is the heaviest path from cell c of a row to the bottom, filled bottom-up.
fun table(tri: List<List<Int>>): Int {
    var best = tri.last()
    println("row ${tri.lastIndex}: ${best.joinToString(" ")}")
    for (row in tri.size - 2 downTo 0) {
        val below = best
        best = tri[row].mapIndexed { c, cell -> cell + maxOf(below[c], below[c + 1]) }
        println("row $row: ${best.joinToString(" ")}")
    }
    return best[0]
}

fun main() {
    println("every path: ${everyPath(triangle)} after ${1 shl (triangle.size - 1)} paths")
    println("greedy walk: ${greedy(triangle)}")
    println("table: ${table(triangle)}")
}

In Kotlin: tri.lastIndex numbers the bottom row, and mapIndexed builds each new row of best from tri[row], cell by cell with its index.

Recorded with Kotlin 2.4.20 on Java 25.0.4.1 on macOS 26 arm64. It runs in your browser with a WebAssembly build on the WASI runner (browser_wasi_shim 0.4.2). To run it yourself: kotlinc Main.kt -include-runtime -d main.jar && java -jar main.jar

Dart 3.13 · main.dart

const triangle = [
  [5],
  [9, 6],
  [4, 6, 8],
  [0, 7, 1, 20],
];

// The heaviest path, by trying all 2^(rows - 1) of them.
int everyPath(List<List<int>> tri) {
  var heaviest = 0;
  for (var moves = 0; moves < 1 << (tri.length - 1); moves++) {
    var (col, total) = (0, tri[0][0]);
    for (var row = 1; row < tri.length; row++) {
      col += (moves >> (row - 1)) & 1; // bit row - 1 set: step down and right
      total += tri[row][col];
    }
    if (total > heaviest) heaviest = total;
  }
  return heaviest;
}

// Always step to the larger of the two numbers below.
int greedy(List<List<int>> tri) {
  var (col, total) = (0, tri[0][0]);
  for (final row in tri.skip(1)) {
    if (row[col + 1] > row[col]) col++;
    total += row[col];
  }
  return total;
}

// best[c] is the heaviest path from cell c of a row to the bottom, filled
// bottom-up.
int table(List<List<int>> tri) {
  var best = tri.last;
  print('row ${tri.length - 1}: ${best.join(' ')}');
  for (var row = tri.length - 2; row >= 0; row--) {
    final below = best;
    best = [
      for (var c = 0; c <= row; c++)
        tri[row][c] + (below[c] > below[c + 1] ? below[c] : below[c + 1]),
    ];
    print('row $row: ${best.join(' ')}');
  }
  return best[0];
}

void main() {
  print(
    'every path: ${everyPath(triangle)} after ${1 << (triangle.length - 1)} paths',
  );
  print('greedy walk: ${greedy(triangle)}');
  print('table: ${table(triangle)}');
}

In Dart: The new row is a list literal with a collection for, and a conditional expression takes the larger of the two cells below.

Recorded with Dart 3.13.5 on macOS 26 arm64. It runs in your browser with a WebAssembly build by dart2wasm 3.13.5. To run it yourself: dart run main.dart