Dynamic Programming — Introduction

Dynamic Programming (DP) is a powerful technique for solving optimization and counting problems where
subproblems overlap and optimal substructure exists. DP transforms exponential-time recursive solutions
into polynomial-time algorithms by storing and reusing intermediate results.

What is Dynamic Programming?

In simple words, dynamic programming is an algorithmic technique that:

• Breaks the problem into smaller subproblems (like recursion),
• Solves each subproblem once,
• Stores results of subproblems (usually in arrays or hash maps), and
• Reuses stored results whenever the same subproblem appears again.

When to use Dynamic Programming?

Use DP when a problem exhibits these two properties:

1. Optimal Substructure: Optimal solution can be composed of optimal solutions of subproblems.
2. Overlapping Subproblems: Same subproblems occur multiple times in the recursion tree.

DP Approaches

There are two main approaches to implement DP:

• Top-Down (Memoization): Start with the original problem, recursively compute results and cache them to avoid recomputation.
• Bottom-Up (Tabulation): Identify the order of computation from smallest subproblems to larger ones and fill a table iteratively.

General Steps to Design a DP Solution

1. Step 1 — Define the State: Decide what parameters uniquely define a subproblem (e.g., index, remaining capacity).
2. Step 2 — Write the Recurrence: Express the solution of a state in terms of other states.
3. Step 3 — Identify Base Cases: Determine trivial states where the answer is known.
4. Step 4 — Choose Implementation: Top-down with memoization or bottom-up tabulation.
5. Step 5 — Optimize Space (if needed): Many DP tables can be optimized to use less memory (rolling arrays).

Key Points / Tips

• Always try to formalize the state clearly — ambiguity in state definition is the most common source of error.
• Draw the recursion tree or DP table for small inputs to verify recurrence and ordering.
• Memoization is easier to write quickly, tabulation can be faster due to reduced recursion overhead.
• Be careful with indices and off-by-one errors in table implementation.
• When optimizing space, make sure the removed dimensions are not required in future computations.

Classic Example: Fibonacci Numbers

Fibonacci demonstrates the difference between naive recursion and dynamic programming.

Naive Recursive (Exponential)

# Python (naive)
def fib(n):
    if n <= 1:
        return n
    return fib(n-1) + fib(n-2)

Time Complexity: O(2^n). This repeats many subcomputations.

Top-Down Memoization

# Python (memoization)
def fib_memo(n, memo=None):
    if memo is None:
        memo = {}
    if n <= 1:
        return n
    if n in memo:
        return memo[n]
    memo[n] = fib_memo(n-1, memo) + fib_memo(n-2, memo)
    return memo[n]

Bottom-Up Tabulation

# Python (tabulation)
def fib_tab(n):
    if n <= 1:
        return n
    dp = [0] * (n+1)
    dp[0], dp[1] = 0, 1
    for i in range(2, n+1):
        dp[i] = dp[i-1] + dp[i-2]
    return dp[n]

Space-Optimized Version

# Python (space optimized)
def fib_opt(n):
    if n <= 1:
        return n
    a, b = 0, 1
    for _ in range(2, n+1):
        a, b = b, a + b
    return b

Another Example: 0/1 Knapsack (Bottom-Up)

Problem: Given weights and values of n items, put items in a knapsack of capacity W to get maximum total value. Each item can be used at most once.

# C++ (0/1 Knapsack - bottom-up)
#include <iostream>
#include <vector>
using namespace std;

int knapSack(int W, const vector<int>& wt, const vector<int>& val, int n) {
    vector<vector<int>> dp(n+1, vector<int>(W+1, 0));
    // dp[i][w] = max value using first i items with capacity w
    for (int i = 1; i <= n; ++i) {
        for (int w = 0; w <= W; ++w) {
            if (wt[i-1] <= w) {
                dp[i][w] = max(dp[i-1][w], val[i-1] + dp[i-1][w - wt[i-1]]);
            } else {
                dp[i][w] = dp[i-1][w];
            }
        }
    }
    return dp[n][W];
}

int main() {
    int W = 50;
    vector<int> val = {60, 100, 120};
    vector<int> wt = {10, 20, 30};
    int n = val.size();
    cout << knapSack(W, wt, val, n) << endl; // Output: 220
    return 0;
}

Time Complexity Table (Common DP Problems)

Common DP Patterns

• Linear DP (array indexed by position): e.g., Fibonacci, climbing stairs.
• Knapsack-like (two-dimensional state: items x capacity): e.g., 0/1 knapsack, subset sum.
• Index + remaining/used parameter: e.g., partition, partition to K subsets.
• Interval DP (i, j): e.g., matrix chain multiplication, burst balloons.
• Bitmask DP (mask, pos): e.g., traveling salesman problem, subset-DP over small n.
• DP on trees (subtree states): e.g., tree DP for independent set, matching.

Applications of Dynamic Programming

• Optimization problems: knapsack, resource allocation, scheduling.
• String problems: longest common subsequence, edit distance, pattern matching.
• Counting problems: number of ways (coin change, paths in grid).
• Graph problems with structure: shortest paths (DAG), Steiner tree variants, bitmask TSP.
• Bioinformatics: sequence alignment, RNA secondary structure prediction.
• Game theory / Decision making: minimax with memoization, optimal strategies.

Pitfalls & How to Avoid Them

• Incorrect state definition — test on small inputs and draw table to verify.
• Memory blow-up — consider whether full table is required or rolling arrays suffice.
• Order of computation — for tabulation ensure dependencies are computed earlier.
• Mutable shared structures with recursion — copy or be careful when reusing arrays/lists for memo keys.

Practice Problems (Good for Learning DP)

1. Fibonacci / Climbing Stairs
2. 0/1 Knapsack
3. Coin Change (counting ways & min coins)
4. Longest Common Subsequence / Longest Common Substring
5. Longest Increasing Subsequence
6. Edit Distance
7. Partition Equal Subset Sum
8. Matrix Chain Multiplication
9. Subset Sum
10. Travelling Salesman (bitmask DP)

Short Walkthrough: Knapsack DP Table (Example)

Suppose weights = [10, 20, 30], values = [60, 100, 120], capacity W = 50.
The DP table dp[i][w] (i = items considered, w = capacity) can be filled row by row.
At the end dp[3][50] = 220 (take items 2 and 3 or 1 and 3 depending on ordering).

More Complete Example: Coin Change (Minimum Coins) — Python

# Python: Minimum coins to make amount (unlimited coins)
import math

def coin_change_min(coins, amount):
    # dp[x] = min coins to make amount x; dp[0] = 0
    dp = [math.inf] * (amount + 1)
    dp[0] = 0
    for coin in coins:
        for x in range(coin, amount + 1):
            dp[x] = min(dp[x], dp[x - coin] + 1)
    return dp[amount] if dp[amount] != math.inf else -1

# Example:
print(coin_change_min([1, 2, 5], 11))  # Output: 3 (5+5+1)

Conclusion

Dynamic Programming is a fundamental paradigm in algorithm design that turns many naive exponential
algorithms into efficient polynomial-time solutions. The key is to identify overlapping subproblems and
an optimal substructure, define a clean state, derive a recurrence, and choose an implementation (top-down
or bottom-up). With practice on classical patterns (linear, knapsack-like, interval, bitmask, tree DP),
you’ll be able to recognize where DP applies and craft efficient solutions.

Start with simple problems (Fibonacci, climbing stairs), then move to knapsack and string DP problems.
Draw tables, practice both memoization and tabulation, and pay attention to space optimization techniques.