Sunday afternoon Problem: Lazy Sequences as a Dynamic Programming Primitive in Kotlin

Dynamic programming is usually taught with mutable arrays and index arithmetic — Kotlin’s generateSequence and sequence { } let you express the same recurrences as infinite, lazily-evaluated streams.

Background

Classic dynamic programming (DP) involves filling a table bottom-up: allocate an array, seed the base case, loop and fill. It works, but the code exposes implementation details — array indexing, loop bounds, off-by-one risks — that have nothing to do with the recurrence relation you’re actually trying to express. The algorithm gets buried in bookkeeping.

Kotlin’s Sequence type is lazy: elements are computed on demand, one at a time, only when a terminal operator (take, first, toList, etc.) pulls them. This maps naturally onto DP recurrences, which are also defined element-by-element from previous values. Instead of a mutable array you manage manually, you get a self-describing stream where each element is a function of earlier ones.

How It Works

generateSequence(seed) { previous -> next } produces an infinite sequence where each element is derived from its predecessor. For recurrences that depend on only one previous value (factorial, powers, running totals) this is sufficient. For recurrences that depend on two or more previous values — Fibonacci, tribonacci, path counts — you pass a Pair or data class as the state carrier, destructure it in the lambda, and let the sequence track the window for you.

The sequence { } builder with yield / yieldAll is more flexible: the lambda is a coroutine, so you can write imperative-looking code that suspends at each yield without allocating the entire series upfront. This is useful when the recurrence has conditional branches or multiple yield points (think coin change variants or staircase problems with variable step sizes).

Crucially, neither generator allocates more than O(window) memory regardless of how far you iterate — compared to a bottom-up DP table that allocates O(n) or O(n²) upfront. For problems where you only need the nth value, not the full table, this is a meaningful difference.

Code

Fibonacci — the textbook case

// Classic mutable DP table — works, but hides the recurrence
fun fibTable(n: Int): Long {
    val dp = LongArray(n + 1)
    dp[0] = 0; dp[1] = 1
    for (i in 2..n) dp[i] = dp[i - 1] + dp[i - 2]
    return dp[n]
}

// Lazy sequence — the recurrence IS the code
val fibonacci: Sequence<Long> = generateSequence(Pair(0L, 1L)) { (a, b) ->
    Pair(b, a + b)          // slide the window forward
}.map { it.first }          // extract the current value

val fib10 = fibonacci.elementAt(10)  // 55
val first20 = fibonacci.take(20).toList()

Staircase problem — n steps, can climb 1 or 2 at a time

// How many distinct ways to reach step n?
// Recurrence: ways(n) = ways(n-1) + ways(n-2)
// Identical structure to Fibonacci, different semantics

val staircaseWays: Sequence<Long> = generateSequence(Pair(1L, 1L)) { (prev2, prev1) ->
    Pair(prev1, prev1 + prev2)
}.map { it.first }

println(staircaseWays.elementAt(5))   // 8  (ways to climb 5 steps)
println(staircaseWays.elementAt(10))  // 89

Coin change — minimum coins, using sequence { } for a richer recurrence

// Build the DP table lazily — each element is min coins for amount i
fun minCoinsSequence(coins: List<Int>): Sequence<Int> = sequence {
    val dp = mutableListOf(0)   // base case: 0 coins for amount 0
    yield(0)

    var amount = 1
    while (true) {
        val minCoins = coins
            .filter { it <= amount }
            .minOfOrNull { dp[amount - it] + 1 }
            ?: Int.MAX_VALUE    // amount unreachable
        dp.add(minCoins)
        yield(minCoins)
        amount++
    }
}

val coins = listOf(1, 5, 6, 9)
val table = minCoinsSequence(coins).take(12).toList()
// index = amount, value = min coins needed
// [0, 1, 2, 3, 4, 1, 1, 2, 2, 1, 2, 2]
println("Min coins for 11: ${table[11]}")  // 2  (9 + 1 + 1... wait: 6+5=11 → 2)

Taking only what you need — O(1) memory for the nth value

// No table allocated — just the sliding window of two longs
fun nthFibonacci(n: Int): Long =
    generateSequence(Pair(0L, 1L)) { (a, b) -> Pair(b, a + b) }
        .elementAt(n)
        .first

Trade-offs & Limitations

The lazy sequence approach works cleanly for 1D recurrences with a fixed, small window. It does not naturally handle 2D DP tables (e.g. longest common subsequence, edit distance) where you need an entire previous row — for those, a mutable array is still the right tool. elementAt(n) on a sequence is O(n) traversal with no caching, so if you call it repeatedly for different values of n on the same sequence, you recompute from the start each time; memoize with toList() or take(n+1).last() instead. The sequence { } builder uses Kotlin coroutines internally, which adds a small overhead per yield — for tight inner loops on large n, benchmark against the array version before committing.

My Take

generateSequence is the cleanest way to express sliding-window DP recurrences in Kotlin — the state carrier pattern with Pair makes the recurrence relation explicit and eliminates index arithmetic entirely. For simple problems (Fibonacci, tribonacci, staircase variants), this is strictly better than a mutable array: less code, no off-by-one risk, and you only compute what you actually consume. For problems where you need random access into the table, or where the recurrence has 2D structure, sequences don’t help and a plain IntArray is fine. The real value is in treating DP not as “fill a table” but as “define a recurrence” — sequences make that framing natural in Kotlin.

Tags: Kotlin, Functional Programming, Dynamic Programming, Sequences

Get in Contact