Back to: Python Data Structure and Algorithims

Dynamic Programming: Understanding Optimized Substructure

In the previous article, we explored overlapping subproblems, the first key requirement for using dynamic programming (DP). In this blog, we’ll cover the second requirement: optimized substructure, another essential concept that makes DP effective.

What is Optimized Substructure?

At first, the term “optimized substructure” might sound complicated, but it’s actually quite simple.

It builds on the idea of subproblems. Once you break a problem into smaller subproblems (and they overlap), these subproblems must satisfy the optimized substructure property:

If you solve the subproblems optimally, you can combine them to form the optimal solution to the overall problem.

Example: Shortest Path in a Weighted Graph

Let’s consider a weighted graph with points A, B, C, and D.

We want to find the lowest-cost path from A to D.

Paths to consider:

A → C → D → cost = 30 + 20 = 50
A → B → D → cost = 10 + 15 = 25

Clearly, the second path is better.

Now let’s break it into subproblems:

Subproblem 1: Shortest path from A → B → 10
Subproblem 2: Shortest path from B → D → 15

By combining these optimal subproblem solutions, we get the optimal solution for A → D, which is 25. ✅

This is a perfect example of optimized substructure.

When Optimized Substructure Fails

Not all problems have this property. Let’s consider finding the highest-cost path from A → D without revisiting nodes.

Suppose the highest-cost path from A → C is not the direct edge, but a longer route going through other nodes.
Similarly, the highest-cost path from C → D may also go around other nodes.

In this scenario, combining the optimal paths of subproblems does not guarantee the optimal solution for A → D. ❌

Key takeaway:

DP works only if subproblems can be combined to form the overall optimal solution.
Problems like shortest path have optimized substructure.
Problems like highest-cost path without revisiting nodes may not have it.

Summary: Requirements for Dynamic Programming

Dynamic programming can only be applied if both requirements are satisfied:

Overlapping Subproblems:
Subproblems repeat, so solving them once and reusing the results is efficient (memoization).
Optimized Substructure:
Solving subproblems optimally allows combining them to solve the overall problem optimally.

Real-World Example

Fibonacci Sequence (DP Example)

Subproblem: fib(n-1) and fib(n-2)
Overlapping subproblems: fib(n-2) repeats many times
Optimized substructure: Optimal solution for fib(n) = fib(n-1) + fib(n-2)

fib_memo = {}

def fibonacci(n):

if n in fib_memo:

return fib_memo[n]

if n <= 1:

return n

fib_memo[n] = fibonacci(n-1) + fibonacci(n-2)

return fib_memo[n]

print(fibonacci(10)) # Output: 55

Conclusion

Dynamic Programming is a powerful problem-solving technique. But it is not universal.

To use DP effectively, a problem must satisfy:

Overlapping Subproblems → you can reuse previously computed results.
Optimized Substructure → combining optimal subproblem solutions gives the overall optimal solution.

Understanding these two properties is the foundation of mastering DP. Once you can identify these in a problem, you’re ready to apply dynamic programming efficiently.