Ways to cross n stepping stones, one or two at a time

Dynamic programming Junior Python 3.13+ Kotlin 2.4+ Reviewed By Best Latest Apps

Predict the output

What does this print?

Python 3.13
calls = 0

def plain(k: int) -> int:
    global calls
    calls += 1
    return 1 if k <= 1 else plain(k - 1) + plain(k - 2)

print(plain(10), calls)

Options

Choose an answer, then open Show answer below to check it.

Show answer

Answer: A 89 177

Right: 89 ways, but the uncached recursion makes 177 calls.

The call count grows like the answer itself, exponentially, while the cached version makes about n calls.

Why not the others?
  • B 89 11. That would be the cached call count, roughly one per value.
  • C 55 109. With ways(0) = 1 the answer for 10 stones is 89.
The call tree for counting ways across five stones, first without a cache (15 calls) and then with one (9 calls, repeats answered from memory).

Steps come from running the Python solution.

Text version

Without a cache:

  • ways(5): call
    • ways(4): call
      • ways(3): call
        • ways(2): call
          • ways(1): call
          • ways(0): call
        • ways(1): call
      • ways(2): call
        • ways(1): call
        • ways(0): call
    • ways(3): call
      • ways(2): call
        • ways(1): call
        • ways(0): call
      • ways(1): call

Result: 8 · 15 calls (call 15)

With a cache:

  • ways(5): call
    • ways(4): call
      • ways(3): call
        • ways(2): call
          • ways(1): call
          • ways(0): call
        • ways(1): memo hit
      • ways(2): memo hit
    • ways(3): memo hit

Result: 8 · 9 calls (call 6, memo hit 3)

30-second answer

From k stones left, your first move leaves k - 1 or k - 2, so ways(k) = ways(k - 1) + ways(k - 2), with ways(0) = ways(1) = 1. Plain recursion repeats the same sub-questions and grows exponentially; caching each answer makes it O(n) time and O(n) memory. A loop with two variables brings memory to O(1).

Practise saying it · 45 s. No recording, just a timer

Explain the stepping-stones DP.

Say your answer out loud, then check which of these points you covered:

  • ways(k) = ways(k-1) + ways(k-2)
  • Cache repeats
  • O(n) time

Deep dive

This is the DP template: write the recursion, notice repeats, cache them.

The answers are Fibonacci numbers shifted by one.

Allowing moves of 1, 2 or 3 adds one more term to the sum; nothing else changes.

Python solution Ran on Python 3.13.5 · mypy --strict
Python 3.13
def stone_ways(n: int) -> int:
    known: dict[int, int] = {}  # memo: stone -> ways from there

    def ways(k: int) -> int:
        if k <= 1:
            return 1  # zero or one stone left: one way
        if k not in known:
            known[k] = ways(k - 1) + ways(k - 2)
        return known[k]

    return ways(n)

Kotlin Ran on Kotlin 2.4.21 · JDK 21.0.12.1
Kotlin 2.4
fun stoneWays(n: Int): Int {
    val known = HashMap<Int, Int>() // memo: stone -> ways
    fun ways(k: Int): Int {
        if (k <= 1) return 1 // zero or one stone left
        return known.getOrPut(k) { ways(k - 1) + ways(k - 2) }
    }
    return ways(n)
}

Common mistakes

  • Wrong base cases, such as ways(0) = 0, which shifts every answer.
  • Recursing without a cache and calling it DP.

Senior take & follow-ups

Draw the call tree for n = 5 with and without the cache; it shows exactly what DP buys.

Follow-up questions

Think of your answer first, then open the hint.

  1. How do you do it in O(1) memory?

    Show hint

    Keep only the last two values and roll them forward in a loop.

  2. What if some stones are missing?

    Show hint

    Set ways to 0 for missing stones; the same sum works.

What each operation costs: Two Dimensional Arrays

From the author

DSA Master - Data & Algorithms

Free on iPhone and iPad: watch 50+ data structures and algorithms step through animations, run the code in the playground, and try the daily challenge.

Get it on the App Store

Suggest a fix if something here is wrong or out of date.