Optimal Substructure

Breaking Down the Problem

To find the nth Fibonacci number, we can break it down into smaller subproblems: finding the (n-1)th and (n-2)th Fibonacci numbers.

Optimal Solution

The optimal solution to the nth Fibonacci number is the sum of the optimal solutions to its subproblems.

Overlapping Subproblems

Redundant Calculations

When calculating the nth Fibonacci number recursively, we encounter the same subproblems multiple times. For example, to calculate F(5), we need to calculate F(4) and F(3). To calculate F(4), we again need to calculate F(3), leading to redundant calculations.

Tabulation

Dynamic programming addresses this by storing the solutions to subproblems in a table  to avoid recalculations.


In essence:

  1. Optimal substructure allows us to break down a problem into smaller, simpler subproblems.
  2. Overlapping subproblems enable us to optimize the solution by storing and reusing the results of these subproblems.
  3. By combining these two properties, dynamic programming provides an efficient approach to solving a wide range of problems.