---
title: "Dynamic Programming: Optimal Substructure and Overlapping Subproblems"
description: "When a problem's best answer is built from best answers to smaller versions, and the same smaller versions keep reappearing, storing each answer once turns an exponential recursion into a polynomial o"
canonical: https://lightmysky.com/learn/computing/dynamic-programming-optimal-substructure-and-overlapping-subproblems-mt__hWkCDnzNY
source: https://lightmysky.com/learn/computing/dynamic-programming-optimal-substructure-and-overlapping-subproblems-mt__hWkCDnzNY.md
retrieved: 2026-09-12
---

> **Agent view.** This is the Markdown twin of the page, for tools and assistants.
> When to use this site, and the call that answers each job: https://lightmysky.com/agent-instructions.md
> API description (OpenAPI 3.1): https://lightmysky.com/openapi.json · Authentication: https://lightmysky.com/auth.md
> Pricing: https://lightmysky.com/pricing.md · Catalog: https://lightmysky.com/llms.txt · Full catalog: https://lightmysky.com/llms-full.txt
> Every machine-readable file on this domain: https://lightmysky.com/.well-known/ai-catalog.json
> Ask for Markdown with `Accept: text/markdown`, a `.md` address, or `?mode=agent`.

# Dynamic Programming: Optimal Substructure and Overlapping Subproblems

When a problem's best answer is built from best answers to smaller versions, and the same smaller versions keep reappearing, storing each answer once turns an exponential recursion into a polynomial one. The two conditions are what decide whether the method applies.

Subject: Computing · Area: Algorithms & Data Structures · Ages 20 to 21
Page: https://lightmysky.com/learn/computing/dynamic-programming-optimal-substructure-and-overlapping-subproblems-mt__hWkCDnzNY

## Ready when they can

- Turn a naive recursive Fibonacci into a memoised one and count the calls saved
- State the subproblem and the recurrence before writing any code
- Say which of the two conditions fails for a problem where the method does not apply

## Lesson: Remember each small answer once

Some problems hide smaller copies of themselves inside. When the best answer to the whole problem is built from best answers to those smaller versions, the problem has optimal substructure. Your first move is always to name the smaller version, called the subproblem, and the rule that combines them, called the recurrence. The smallest version you answer directly is the base case. For Fibonacci the subproblem is fib(k) for k below n, with fib(k) = fib(k-1) + fib(k-2).

**Example.** Watch naive fib(20) run and it makes over 20,000 calls, because it recomputes the same small values again and again. The memoised version computes each of fib(0) through fib(20) exactly once, which is 21 values, each in constant extra work. Same recurrence, same answers, hugely less work, because no value is ever computed twice.

The second condition is overlap: the same smaller versions must keep reappearing. When they do, you store each answer the first time you compute it and reuse it later, which is called memoising. Moving a stack of rings never repeats a smaller move, since each move happens once, so storing answers there saves nothing.

**Tip.** Before any code, ask two questions. One, is the best answer built from best answers to smaller versions. Two, do those smaller versions repeat. Mergesort fails the second, since its pieces are all distinct. The longest simple path fails the first, since reusing vertices breaks the buildup. For rod-cutting, state the subproblem and recurrence first, then memoise.

**Recap.** Name the subproblem and recurrence, check both conditions, and store each repeated answer once.

## Practice

8 questions on this page, each with its working shown.

## Needs first

- [Recurrence Relations and the Master Theorem](https://lightmysky.com/learn/computing/recurrence-relations-and-the-master-theorem-mt_aOvLPV7rR8)
- [Dictionaries: Values Found by Key](https://lightmysky.com/learn/computing/dictionaries-values-found-by-key-mt_mofpj0n5AM)

## Opens up

- [Markov Decision Processes: States, Actions and Return](https://lightmysky.com/learn/computing/markov-decision-processes-states-actions-and-return-mt_bTCO27sgc6)
- [Dynamic Programming on Two Sequences](https://lightmysky.com/learn/computing/dynamic-programming-on-two-sequences-mt_uNUgHcKKQN)