Faangprep Logo
Log inStart free
Browse curriculum

Dynamic Programming

Dynamic programming is an algorithmic paradigm that solves complex problems by breaking them into simpler overlapping subproblems and storing their results.

Fib(k) = Fib(k-1) + Fib(k-2) is a correct definition and a terrible program: it asks for the same subproblem over and over, and there are only n+1 of them. The table counts every call. Switch to MEMO and watch each row collapse to one or two.

READY

k

calls

5
4
3
2
1
0

Total

0

With cache

9

Depth

0

 

Fib(5) straight from the definition: Fib(k) = Fib(k-1) + Fib(k-2). Nothing is remembered between calls, so every subproblem is solved again wherever it turns up.

Next

Fib(5) — first time this subproblem has been asked for.

N

Recursion

Intuition

Imagine you have to write down the solution to a complex math problem. If you see the same problem again later, would you solve it from scratch? No, you'd check your previous notes! Dynamic Programming (DP) is exactly that: remembering answers to the past so you don't repeat work.

Concept

Dynamic Programming applies when a problem has two key properties:

  • Overlapping Subproblems: The problem can be broken down into smaller, repetitive subproblems. (e.g., Fibonacci: F5 needs F4 and F3, F4 needs F3 and F2 - F3 repeats).
  • Optimal Substructure: The optimal solution to the problem can be constructed from optimal solutions of its subproblems.

There are two main approaches:

  • Memoization (Top-Down): Start from the main problem, recurse down, and cache results.
  • Tabulation (Bottom-Up): Start from the smallest subproblems, build a table (array/matrix) up to the main problem.

How it Works

The Core Workflow:

  1. Identify State: What variables define a subproblem? (e.g., index, capacity).
  2. Recurrence Relation: How does the current state depend on previous states? (e.g., dp[i] = dp[i-1] + dp[i-2]).
  3. Base Cases: What are the trivial solutions? (e.g., dp[0] = 0).
  4. Order of Computation: Decide if you want to recurse (Memoization) or iterate (Tabulation).

Step-by-Step Breakdown

Visualizing the difference:

  • Recursion (Without DP): Grows like a tree, re-calculating the same nodes many times. O(2n).
  • Memoization: Prunes the recursion tree. If a node is visited, return stored value. O(N).
  • Tabulation: Fills a table row by row or cell by cell. No recursion overhead. O(N).

When to Use

Common Scenarios:

  • Maximizing or Minimizing valid combinations (e.g., Knapsack, Longest Common Subsequence).
  • Counting total arrangements (e.g., Coin Change, Unique Paths).
  • String edit distance problems.
  • Graph problems on Directed Acyclic Graphs (DAGs).

When NOT to Use

  • No Overlap: If the problem splits into non-overlapping subproblems, use Divide and Conquer (e.g., Merge Sort).
  • No Optimal Substructure: If the best answer to the whole problem cannot be assembled from best answers to its subproblems. The classic example is the longest simple path in a general graph: the longest path's pieces are not themselves longest paths. The same applies when subproblems depend on each other in a cycle.

How to Identify

"Maximize/Minimize value", "Count ways to...", "Longest/Shortest sequence", "Can you reach...?".

Preparing for interviews? This topic is also taught as a pattern:

Intro to Dynamic Programming

Applying for software engineering roles? Free, no sign-up:

AI resume checker — match your resume to the job description
Previous

Perfect Hashing

Next

Fibonacci Sequence

Frequently Asked Questions

What is Dynamic Programming?

Dynamic Programming is an algorithmic technique for solving complex problems by breaking them down into simpler subproblems and storing the results of these subproblems (memoization) to avoid redundant computations.

Memoization vs Tabulation?

Memoization is a Top-Down approach using recursion and a cache. Tabulation is a Bottom-Up approach using a table (array) and iteration to build up the solution.

When to use DP?

Use DP when a problem has "Overlapping Subproblems" (the same work is repeated) and "Optimal Substructure" (the optimal solution of the problem contains optimal solutions of its subproblems).