Back to course

Lesson 52: Introduction to Dynamic Programming (DP)

Algorithms: From Zero to Hero (A Beginner's Guide)

52. Introduction to Dynamic Programming (DP)

Dynamic Programming is a powerful technique primarily used for optimization problems. It avoids redundant computations by storing the results of subproblems.

When is DP applicable?

DP is suitable for problems exhibiting two key properties:

  1. Optimal Substructure: An optimal solution to the problem can be constructed from optimal solutions to its subproblems (similar to Greedy/D&C).
  2. Overlapping Subproblems: The same subproblems are solved repeatedly by a recursive algorithm. This redundancy is what DP targets.

DP vs. Divide and Conquer

  • D&C: Subproblems are independent (e.g., sorting the left side of Merge Sort doesn't affect sorting the right side).
  • DP: Subproblems are interdependent and overlap (e.g., calculating Fibonacci(5) requires Fibonacci(4) and Fibonacci(3). Calculating Fibonacci(4) also requires Fibonacci(3)).