Skip to content

Dynamic Programming

Dynamic Programming (DP) is a powerful technique for solving complex problems by breaking them down into simpler, overlapping subproblems. It is especially useful when the same subproblems are solved multiple times.

Key Properties

A problem is suitable for dynamic programming if it exhibits:

  • Optimal Substructure: The optimal solution to the problem can be constructed from optimal solutions to its subproblems.
  • Overlapping Subproblems: The problem can be divided into subproblems that are reused several times.

DP Approaches

Dynamic programming algorithms are generally implemented in two main ways:

1. Top-Down (Memoization)

  • Start with a recursive solution.
  • Use a table (such as an array or hash map) to store results of subproblems.
  • Before solving a subproblem, check if its result is already stored. If so, reuse it; otherwise, compute and store it.
  • Memoization is ideal when only a subset of all possible subproblems needs to be solved (sparse state space), or when the order of computation is irregular.

2. Bottom-Up (Tabulation)

  • Solve the smallest subproblems first, then iteratively build up solutions to larger subproblems.
  • Use loops instead of recursion, storing all results in a table.
  • Tabulation works best when most or all subproblems need to be solved (dense state space), and allows discarding results that are no longer needed to save memory.