# Dynamic Programming (DP)

Dynamic Programming is a method for solving complex problems by breaking them down into simpler subproblems. It is applicable to problems exhibiting the properties of **overlapping subproblems** and **optimal substructure**.

## 1. Core Concepts

*   **Overlapping Subproblems:** The problem can be broken down into subproblems which are reused several times. (e.g., in Fibonacci, `fib(5)` needs `fib(4)` and `fib(3)`, and `fib(4)` needs `fib(3)` and `fib(2)`).
*   **Optimal Substructure:** The optimal solution of the main problem can be constructed from the optimal solutions of its subproblems.

## 2. Approaches

There are two main ways to implement DP:

### Top-Down (Memoization)
Start from the main problem and break it down. If you solve a subproblem, store the result ("memoize" it) so you don't have to solve it again. This is essentially **Recursion + Caching**.

```python
# Fibonacci with Memoization
memo = {}

def fib(n):
    if n in memo:
        return memo[n]
    if n <= 1:
        return n
    
    memo[n] = fib(n-1) + fib(n-2)
    return memo[n]
```

### Bottom-Up (Tabulation)
Start with the smallest subproblems and build up to the main problem. This is usually done with **Iteration** (loops) and filling up a table (array).

```python
# Fibonacci with Tabulation
def fib(n):
    if n <= 1:
        return n
    
    table = [0] * (n + 1)
    table[1] = 1
    
    for i in range(2, n + 1):
        table[i] = table[i-1] + table[i-2]
        
    return table[n]
```

## 3. Common Problems

*   Fibonacci Sequence
*   Knapsack Problem
*   Longest Common Subsequence
*   Shortest Path (e.g., Bellman-Ford, Floyd-Warshall)

[[programming/algorithms]]