Dynamic programming and memoisation

Dynamic programming solves a problem by storing the answers to overlapping smaller problems so each is computed only once.

🔎 Unravel this example Prerequisites (1)

Learn these first

Recursion

At a glance

Mental model

Writing down every intermediate sum on a notepad while adding a long column of figures, so that when you need "the sum so far" again you read it instead of adding everything again.

What happens, in order

1Top-down (memoisation): keep recursion but cache results in a map or array: if (memo[n] != 0) return memo[n]; memo[n] = f(n-1) + f(n-2);
2Bottom-up (tabulation): fill an array dp[i] from the smallest cases up: dp[0] = 0; dp[1] = 1; for (i = 2..n) dp[i] = dp[i-1] + dp[i-2]
3Recipe: define what dp[i] means (in words), write the recurrence ("how does dp[i] follow from smaller ones"), set the base cases, and decide the order of filling
4Classic problems: Fibonacci, climbing stairs, coin change, longest common subsequence, knapsack, edit distance, grid paths

Remember

It applies when subproblems overlap and the optimal solution is built from optimal sub-solutions
Space can often shrink: Fibonacci needs only the last two values (prev, cur) instead of the whole array; row-by-row problems need one or two rows
Memoisation trades memory for time: with n states and constant work per state, the time is O(n) instead of exponential

Watch out

Defining the state vaguelyWrong base casesMutating the map inside computeIfAbsentOverflowing int in the table

Example (highlighted lines explain it)

import java.util.*;public class Dp {  static long fibMemo(int n, long[] memo) {    if (n <= 1) return n;    if (memo[n] != 0) return memo[n];    return memo[n] = fibMemo(n - 1, memo) + fibMemo(n - 2, memo);  }  static int coins(int[] coins, int amount) {    int[] dp = new int[amount + 1];    Arrays.fill(dp, Integer.MAX_VALUE);    dp[0] = 0;    for (int a = 1; a <= amount; a++)      for (int c : coins)        if (c <= a && dp[a - c] != Integer.MAX_VALUE) dp[a] = Math.min(dp[a], dp[a - c] + 1);    return dp[amount] == Integer.MAX_VALUE ? -1 : dp[amount];  }}

Read the full explanation (about 1 min)

Dynamic programming solves a problem by storing the answers to overlapping smaller problems so each is computed only once. It turns an exponential recursion (naive Fibonacci) into a linear loop.

A mental model

Writing down every intermediate sum on a notepad while adding a long column of figures, so that when you need "the sum so far" again you read it instead of adding everything again.

How it works

Top-down (memoisation): keep recursion but cache results in a map or array: if (memo[n] != 0) return memo[n]; memo[n] = f(n-1) + f(n-2);.

Bottom-up (tabulation): fill an array dp[i] from the smallest cases up: dp[0] = 0; dp[1] = 1; for (i = 2..n) dp[i] = dp[i-1] + dp[i-2].

Recipe: define what dp[i] means (in words), write the recurrence ("how does dp[i] follow from smaller ones"), set the base cases, and decide the order of filling.

Classic problems: Fibonacci, climbing stairs, coin change, longest common subsequence, knapsack, edit distance, grid paths.

Going deeper

It applies when subproblems overlap and the optimal solution is built from optimal sub-solutions. If subproblems do not overlap (merge sort), plain recursion is enough.

Space can often shrink: Fibonacci needs only the last two values (prev, cur) instead of the whole array; row-by-row problems need one or two rows.

A memo HashMap with computeIfAbsent that recursively modifies the same map throws ConcurrentModificationException in Java; use an explicit get and put, or an array.

Under the hood

Memoisation trades memory for time: with n states and constant work per state, the time is O(n) instead of exponential. Arrays are much faster than boxed Map<Integer, Long> due to no hashing or boxing.

Common mistakes

Defining the state vaguely.
Wrong base cases.
Mutating the map inside computeIfAbsent.
Overflowing int in the table.

How Unravel recognises it

When you paste code, Unravel looks for these signs of dynamic programming and memoisation. Spotting them yourself is a good habit when you read unfamiliar code:

Language constructs: recursion

Part of a learning path

Algorithms and data structures · previous: Two pointers and sliding window · next: Linked lists

Related concepts

RecursionJava language Time complexity (Big O)Java language Arrays and the Arrays utilitiesJava language

Frequently asked questions

What is Dynamic programming and memoisation?

Dynamic programming solves a problem by storing the answers to overlapping smaller problems so each is computed only once. It turns an exponential recursion (naive Fibonacci) into a linear loop.

What are the most common mistakes with Dynamic programming and memoisation?

Defining the state vaguely. Wrong base cases. Mutating the map inside computeIfAbsent. Overflowing int in the table.

How can I see Dynamic programming and memoisation in real code?

Paste your own Java into Unravel and it will point out where dynamic programming and memoisation appears, explain how it works at the detail level you choose, and draw the flow of the code around it.