Memoization Coding Problems: 6 Questions with Solutions

How memoization works, step by step

1. Plain recursion for fib(5) recomputes the same smaller values again and again. Memoization keeps a table: before working anything out, a call checks the memo, and after working it out, it writes the answer there.
2. Nothing is cached yet, so fib(5) calls fib(4), which calls fib(3), which calls fib(2), which calls fib(1): always the n − 1 branch first. fib(1) is a base case and returns 1 at once.
3. fib(0) returns 0, so fib(2) = fib(1) + fib(0) = 1 + 0 = 1. Before returning, fib(2) writes its answer to memo[2], so no later call has to work it out again.
4. fib(1) returns 1, so fib(3) = fib(2) + fib(1) = 1 + 1 = 2, written to memo[3] on the way out. The base cases cost O(1) anyway, so only n ≥ 2 is cached.
5. fib(4) needs fib(2) next. memo[2] = 1 is already there, so the call returns at once: the 2 calls a plain fib(2) would make below it never happen.
6. fib(4) = fib(3) + fib(2) = 2 + 1 = 3, written to memo[4]. The memo now holds every value below fib(5).
7. fib(5) needs fib(3) next. memo[3] = 2 is already there, so the call returns at once: the 4 calls a plain fib(3) would make below it never happen.
8. fib(5) = fib(4) + fib(3) = 3 + 2 = 5, after 9 calls where plain recursion makes 15. Each fib(k) was computed once and every repeat was an O(1) lookup, so the time is O(n), with O(n) memory for the memo and the stack.

Memoization study plan

All 6 Memoization problems (2 easy, 2 medium and 2 hard) over 4 days, about 3 h 45 min in all — the pattern first, then easiest to hardest. Then move on to Digit DP.

Day 1

Learn the pattern: read the essentials and step through the walkthrough above, then solve these 2.

• Climbing Stairs Easy
• N-th Tribonacci Number Easy

Day 2

Medium problems: the same pattern with one twist each. Name the twist before you code.

• Sort Integers by The Power Value Medium
• Longest Binary Subsequence Less Than or Equal to K Medium

Day 3

Hard problems: the pattern combined with a second idea. Give each a full attempt before reading the editorial.

• Number of Increasing Paths in a Grid Hard

Day 4

Another hard one. If it beats you after a real attempt, read the editorial, then solve it again tomorrow from memory.

• Number of Distinct Roll Sequences Hard

Next topic: Digit DP

Memoization: the essentials

When to reach for it

A recursion that is correct but slow because the same arguments keep coming back: a Fibonacci-like recurrence, the paths onward from each cell, Collatz step counts shared by many starting values. The arguments that change are the state; if the distinct states fit in memory, cache each answer. A cache also spares you the filling order a bottom-up table needs — that form is on Dynamic Programming.

The pattern

Write the recursion with its base cases, make sure everything the result depends on is an argument, then cache: Python's functools.cache does it in one line; elsewhere use a hash map keyed by the arguments, or an array holding a sentinel such as −1.

from functools import cache

def count_increasing_paths(grid):       # strictly increasing paths, any length
    m, n = len(grid), len(grid[0])
    @cache
    def paths_from(r, c):               # the cell alone, plus every way onward
        total = 1
        for nr, nc in ((r + 1, c), (r - 1, c), (r, c + 1), (r, c - 1)):
            if 0 <= nr < m and 0 <= nc < n and grid[nr][nc] > grid[r][c]:
                total += paths_from(nr, nc)
        return total
    return sum(paths_from(r, c) for r in range(m) for c in range(n))

Cost

Distinct states × work per state, plus a cache entry per state: O(m × n) above. The first call can recurse as deep as the longest chain of states, past Python's 1,000-frame default on large inputs.

Common mistakes

• Depending on state outside the arguments — a visited set, a running total — so a cached answer is reused where it no longer holds.
• A mutable argument as the key: Python refuses a list. Pass indices or tuples.
• A memo kept in a global or a class field and not cleared between test cases.
• Caching a recursion whose arguments rarely repeat, which spends memory for nothing.

Start with

• Climbing Stairs: the recursion that is exponential without a cache.
• Sort Integers by The Power Value: one cache shared by every starting value.
• Number of Increasing Paths in a Grid: a memo where a table's order would be awkward.

All memoization problems

Easy (2)

• N-th Tribonacci Number Math, Dynamic Programming
• Climbing Stairs Math, Dynamic Programming

Medium (2)

• Longest Binary Subsequence Less Than or Equal to K String, Greedy, Dynamic Programming
• Sort Integers by The Power Value Dynamic Programming, Sorting

Hard (2)

• Number of Distinct Roll Sequences Dynamic Programming
• Number of Increasing Paths in a Grid Array, Matrix, Dynamic Programming

Companies that ask memoization problems

• Amazon 5 problems on memoization
• Google 5 problems on memoization
• Adobe 2 problems on memoization
• Flipkart 1 problem on memoization
• Microsoft 1 problem on memoization

Other topics

• Arrays 667 problems
• Strings 282 problems
• Math 213 problems
• Hash Table 202 problems
• Dynamic Programming 195 problems
• Greedy 163 problems
• Sorting 156 problems
• Two Pointers 113 problems
• Matrix 107 problems
• Binary Search 95 problems
• Simulation 88 problems
• Bit Manipulation 83 problems