Interview OS
Back to Algorithms & Data Structures

Library

Dynamic programming

Optimal substructure + memoization.

Optimization

Overview

Dynamic programming decomposes a problem into overlapping subproblems solved once and reused. This topic drills defining state, writing the recurrence, and choosing top-down memoization vs bottom-up tabulation.

How it works

Optimization
StateRelateFillOutputDefine dpdp[i]RecurrencetransitionMemo/tableO(states)Answer
ClientServiceDataEdge

Step by step, with examples

  1. 1

    Define dp

    • State meaning plus the base case.
  2. 2

    Recurrence

    • Build from smaller states.
  3. 3

    Memo/table

    • Top-down memo or bottom-up table.
  4. 4

    Answer

    • Read the target state.
    • Example: knapsack, LIS

Overview

Break a problem into overlapping subproblems and cache results — top-down (memo) or bottom-up (tabulation).

Common pitfalls

  • Wrong state definition
  • Iterating dimensions in the wrong order

Where this content comes from

For full transparency, this content is curated and verified from these sources:

CLRS — Introduction to AlgorithmsCurated competitive-programming archivesOppZen-authored algorithm guides