DP Theory: Overlapping Subproblems & Optimal Substructure

Dynamic Programming Theory

Welcome to Dynamic Programming (DP), a powerful algorithmic technique for solving complex problems by breaking them down into simpler, overlapping subproblems. DP is all about solving each subproblem only once and storing its solution, thereby avoiding redundant computations.

---

1. The Two Hallmarks of DP Problems

Dynamic Programming is applicable when a problem exhibits two key properties:

• Optimal Substructure: A problem has optimal substructure if its optimal solution can be constructed from the optimal solutions of its subproblems. For example, the shortest path to a destination is composed of shortest paths to intermediate waypoints.

• Overlapping Subproblems: The problem can be broken down into subproblems that are reused several times. A naive recursive solution would solve these subproblems over and over again. DP solves each subproblem just once.

---

2. The Two Approaches to DP

There are two main ways to implement a Dynamic Programming solution:

2.1. Memoization (Top-Down)

This approach is a "top-down" method that works by starting with the original problem and breaking it down recursively. The results of the subproblems are stored in a cache (like a map or an array) so that they don't have to be recomputed.

• How it works: A standard recursive function is augmented with a cache. Before computing, it checks if the result is already in the cache. If so, it returns the cached value. Otherwise, it computes the result, stores it in the cache, and then returns it.

2.2. Tabulation (Bottom-Up)

This approach is a "bottom-up" method that works by solving the smallest possible subproblems first and then building up to the solution of the original problem. The results are stored in a table (e.g., a 1D or 2D array).

• How it works: The table is filled out iteratively, starting from the base cases. Each entry in the table is computed based on the values of previous entries.

---

3. A 4-Step Process for Solving DP Problems

When faced with a potential DP problem, you can follow this general process:

1. Characterize the Structure: Understand how an optimal solution is composed of optimal solutions to subproblems.
2. Define the State: Define what a "subproblem" is and what parameters are needed to describe it (e.g., dp[i] could be the maximum value up to index i).
3. Define the Recurrence: Write a recurrence relation that expresses the solution to a subproblem in terms of the solutions to smaller subproblems.
4. Build the Solution: Implement the solution, either top-down (memoization) or bottom-up (tabulation), starting from the base cases.

---

Key Takeaway: Dynamic Programming is an optimization technique for problems with optimal substructure and overlapping subproblems. By solving each subproblem only once, either through top-down memoization or bottom-up tabulation, it can dramatically improve the efficiency of an algorithm.