Dynamic Programming: Intro, Memoization, and Tabulation

Dynamic Programming (DP) is a method for solving complex problems by breaking them down into simpler subproblems and solving each of those only once. It is especially useful for optimization problems where the same subproblems appear repeatedly.

---

When to Use Dynamic Programming

Dynamic Programming is ideal when:

• The problem can be divided into overlapping subproblems.
• The problem has an optimal substructure (the optimal solution can be built from optimal solutions of subproblems).

---

Memoization (Top-Down Approach)

Memoization is an optimization technique where you store the results of expensive function calls and return the cached result when the same inputs occur again.

Example: Fibonacci with Memoization

import java.util.HashMap;

public class Fibonacci {
  private HashMap<Integer, Integer> memo = new HashMap<>();

  public int fib(int n) {
    if (n <= 1) return n;
    if (memo.containsKey(n)) return memo.get(n);
    int result = fib(n - 1) + fib(n - 2);
    memo.put(n, result);
    return result;
  }
}

This approach reduces the exponential time complexity of the naive recursive Fibonacci to linear time.

---

Tabulation (Bottom-Up Approach)

Tabulation builds up the solution iteratively using a table (usually an array). It avoids recursion entirely.

Example: Fibonacci with Tabulation

public int fib(int n) {
  if (n <= 1) return n;
  int[] dp = new int[n + 1];
  dp[0] = 0;
  dp[1] = 1;
  for (int i = 2; i <= n; i++) {
    dp[i] = dp[i - 1] + dp[i - 2];
  }
  return dp[n];
}

Tabulation is usually more efficient in terms of space and avoids the overhead of function calls.

---

Choosing Between Memoization and Tabulation

• Use memoization if the recursive structure of the problem is intuitive and you prefer a top-down style.
• Use tabulation if you want better performance and can write the solution in a bottom-up way.

---

Common DP Problems

• Fibonacci sequence
• Longest Common Subsequence (LCS)
• 0/1 Knapsack Problem
• Coin Change
• Matrix Chain Multiplication
• Edit Distance

---

Dynamic Programming is a key technique in algorithm design. Mastering both memoization and tabulation will significantly improve your ability to solve complex problems efficiently.