juniorDynamic Programming

What are the two key attributes of a DP problem?

Updated Apr 28, 2026

Short answer

The two key attributes of a Dynamic Programming problem are overlapping subproblems and optimal substructure. Overlapping subproblems mean the same smaller problems are solved multiple times, while optimal substructure means the optimal solution can be built from optimal solutions of smaller subproblems. When both properties exist, Dynamic Programming can avoid repeated work and efficiently solve the problem.

Deep explanation

Dynamic Programming (DP) is a technique for solving complex problems by breaking them into smaller subproblems, solving those subproblems once, and storing their results for reuse.

A problem is a good candidate for Dynamic Programming when it has these two important properties:

  1. Overlapping Subproblems
  2. Optimal Substructure

Both are necessary because they solve different parts of the DP process.

---

1. Overlapping Subproblems

A problem has overlapping subproblems when the same smaller problems are solved repeatedly during the computation.

Instead of recalculating the same answer multiple times, DP stores the result and reuses it.

Example: Fibonacci

The Fibonacci recurrence is:

TEXT
F(n) = F(n - 1) + F(n - 2)

A simple recursive implementation:

Python
def fibonacci(n):
    if n <= 1:
        return n


    return fibonacci(n - 1) + fibonacci(n - 2)

Calling:

Python
fibonacci(5)

creates a recursion tree:

TEXT
F(5)
              /       \
           F(4)       F(3)
          /   \       /   \
       F(3)  F(2)  F(2)  F(1)

Notice that:

TEXT
F(3)
F(2)

are calculated more than once.

These repeated calculations are overlapping subproblems.

DP solves this by storing results:

Python
memo[3] = 2
memo[2] = 1

When the same value is needed again, it is retrieved instead of recomputed.

---

2. Optimal Substructure

A problem has optimal substructure when the optimal solution to the entire problem can be created using optimal solutions to smaller subproblems.

In simpler terms:

The best answer for a large problem contains the best answers for smaller versions of that problem.

Example: Shortest Path

Suppose the shortest route from A to C is:

TEXT
A → B → C

For this route to be optimal:

  • The path from A to B must be the shortest path from A to B.
  • The path from B to C must be the shortest path from B to C.

If a shorter A → B route existed, we could replace that section and create an even shorter A → C route.

Therefore, the solution contains optimal solutions to smaller problems.

---

How the Two Properties Work Together

Consider the Coin Change problem:

Find the minimum number of coins needed to make a given amount.

For example:

TEXT
Coins: [1, 2, 5]
Amount: 5

The answer is:

TEXT
5 = 5

using one coin.

To solve larger amounts, we solve smaller amounts:

TEXT
Best(5)
= 1 + Best(4)
= 1 + Best(3)
= ...

This works because:

Optimal Substructure

The best way to make amount 5 depends on the best ways to make smaller amounts.

Overlapping Subproblems

The same amounts are calculated repeatedly:

TEXT
Best(3)
Best(2)
Best(1)

DP stores these answers and avoids recalculating them.

---

Dynamic Programming Approaches

Once a problem has both properties, we can implement DP in two common ways.

Memoization (Top-Down)

Uses recursion and stores results:

Python
def solve(n, memo={}):
    if n in memo:
        return memo[n]


    # calculate result


    memo[n] = result
    return result

Advantages:

  • Natural extension of recursive solutions.
  • Only computes required states.

Disadvantages:

  • Uses recursion stack.
  • Can cause stack overflow for very deep problems.

---

Tabulation (Bottom-Up)

Uses iteration and builds solutions from smaller states:

Python
dp[0] = base_case


for i in range(1, n + 1):
    dp[i] = calculate_from_previous_states

Advantages:

  • Avoids recursion overhead.
  • Often easier to optimize for memory.

Disadvantages:

  • May compute states that are not needed.
  • Requires knowing the correct order of computation.

---

Real-world example

A financial application calculates the maximum profit from buying and selling stocks over multiple days.

The problem can be solved with DP because:

  • The best profit on day n depends on the best profits from previous days (optimal substructure).
  • The same previous-day calculations are needed repeatedly (overlapping subproblems).

Example:

Python
def max_profit(prices):
    previous = 0
    current = 0


    for price in prices:
        best_today = max(current, previous + price)
        previous = current
        current = best_today


    return current

The algorithm stores previous results instead of recomputing possible decisions.

Common mistakes

  • * Thinking that having smaller subproblems automatically means a problem can use DP.
  • * Confusing overlapping subproblems with optimal substructure.
  • * Forgetting that DP requires both properties together in most cases.
  • * Using DP when subproblems are independent and do not repeat.
  • * Assuming optimal substructure means a greedy solution will always work.
  • * Ignoring repeated calculations in recursive solutions.
  • * Storing results without identifying the correct DP state.

Follow-up questions

  • What is the difference between overlapping subproblems and optimal substructure?
  • Can a problem have overlapping subproblems but not be solved using DP?
  • Can greedy algorithms have optimal substructure?
  • How do you recognize a DP problem in an interview?
  • Why is Fibonacci considered a classic DP problem?
  • What happens if a problem only has optimal substructure but no overlapping subproblems?

More Dynamic Programming interview questions

View all →