Memoization (top-down) starts from the original problem and recursively breaks it down, caching results. Tabulation (bottom-up) starts from base cases and iteratively builds up to the target. Memoization is easier to code from a recurrence but risks stack overflow on large inputs. Tabulation is faster when all subproblems must be computed but harder to derive directly.

Count the independent variables that change between subproblem calls. If only one parameter changes (like remaining amount or array index), 1D suffices. If two independent constraints change (like position in two strings, or index + weight capacity), you need 2D. Add dimensions only when a constraint truly restricts future choices.

Overlapping subproblems means the same subproblem is solved multiple times in the recursion tree. Fibonacci's naive recursion computes `fib(3)` dozens of times — that's overlap. DP exploits this by storing computed results. Without overlap, divide-and-conquer (like mergesort) is a better fit. The two prerequisites for DP are: optimal substructure and overlapping subproblems.

Negative values break DP assumptions for min/max problems because base cases initialize to 0 or infinity. Options: (1) Offset the state space by shifting all values positive. (2) Use a sentinel value (like -inf for max problems). (3) For knapsack variants, handle negative weights by reordering items or splitting the DP table into positive and negative halves. Always validate edge cases with negative inputs.

Store backtracking choices alongside DP values. For LCS, instead of storing just length, also store which direction (diagonal/up/left) led to the optimal value. After computing the table, trace back from dp[m][n] following the stored directions. For knapsack, store a boolean `take[i][w]` that's true when item i was included. Memory overhead is usually O(n*m) additional storage, which is acceptable for most problems.

State compression reduces memory by storing only the necessary rows or states at any point. If `dp[i]` only depends on `dp[i-1]`, you can keep just two 1D arrays. For 2D DP where `dp[i][j]` depends on the previous row, you can use a single 1D array updated in-place (with careful reverse iteration). The classic example is 0/1 knapsack optimized to O(capacity) space from O(n * capacity).

Optimal substructure exists when you can break down the problem and express the optimal solution as a function of optimal solutions to smaller subproblems. Test: after making a decision, does the remaining problem become a smaller version of the same problem? For shortest path: the optimal A→C path through B equals optimal A→B plus optimal B→C. If your recurrence builds solution from arbitrary (non-optimal) subproblem solutions, the problem lacks optimal substructure.

Overlapping subproblems: the same subproblem is computed multiple times (e.g., fib(3) in Fibonacci recursion). This creates inefficiency that DP eliminates by caching. Optimal substructure: the optimal solution to a problem can be constructed from optimal solutions of subproblems. Both are required for DP to apply—overlap alone just means divide-and-conquer with caching would help, but optimal substructure is what makes the recurrence work.

Ask: "What is the last decision I need to make?" Then express the answer in terms of subproblems. For coin change: "What coin do I use last?" gives recurrence `dp[i] = min(dp[i-coin] + 1)`. For LCS: "Do the current characters match?" gives branching recurrence. Identify the state variables that represent your subproblem space, then express the answer for state (i,j) in terms of solutions to states with smaller parameters.

Top-down (memoization) is preferred when: the subproblem graph is sparse (you don't need most states), recursive structure maps naturally to the problem, or you want to avoid computing unnecessary states. Bottom-up (tabulation) is preferred when: all states are needed (dense recursion graph), you need the fastest possible iteration, or you're implementing space-optimized solutions. Top-down is often easier to derive from a recurrence; bottom-up can be optimized better.

Complex dependencies (like dp[i][j][k] depending on dp[i-1][j][k-1], dp[i][j-1][k], dp[i][j][k-1]) require careful ordering. Draw the dependency graph to visualize which states contribute to which. Ensure inner loops iterate in the correct direction—for in-place updates, iterate backwards to avoid corrupting values needed later. Consider whether all dimensions need to be fully computed or if you can prune the state space.

Minimal: removing any variable from the state would cause different subproblems to collapse into the same representation. Sufficient: the state contains enough information to make optimal decisions for the remaining problem. For example, in 0/1 knapsack, `dp[i][w]` is minimal and sufficient—you need both the item index and remaining weight capacity. If you drop either, you lose critical decision-making information.

Start by testing with small inputs and brute-force enumeration. Compare your DP result against exhaustive search for n ≤ 10. If wrong, check: (1) Does your state uniquely identify subproblems? (2) Is your recurrence correct? (3) Are base cases handled? (4) Is tabulation order correct? Add debug output to print dp table and trace where values diverge from expected. Often the issue is subtle—like treating index as value or missing a constraint dimension.

No—optimal substructure is a prerequisite for DP. Without it, building optimal solutions from optimal subproblem solutions doesn't work. In such cases, exhaustive search or approximation algorithms may be needed. Some problems that appear to have DP structure actually don't; the greedy trap scenario in the failure section illustrates this. Always verify optimal substructure exists before committing to a DP approach.

Reducing state space directly reduces both time and space. If you compress n^2 states to O(n), you cut both dimensions. For example, 0/1 knapsack reduces from O(n*capacity) to O(capacity) via state compression. Time still depends on how many transitions each state processes—if each state considers k options, complexity is O(k * states). Space optimization typically doesn't affect asymptotic time, only memory usage.

1. Optimal Substructure: The optimal solution can be constructed from optimal solutions of subproblems. 2. Overlapping Subproblems: The same subproblem is solved multiple times in naive recursion, creating opportunity for caching. Both are necessary—optimal substructure enables correct recurrence, overlapping subproblems provides the efficiency gain. Problems like Fibonacci have both; problems like DFS/traversal may have overlap but lack optimal substructure.

Ask yourself: "What minimum information do I need to make optimal decisions for the remaining problem?" For the coin change problem, we need the target amount. For LCS, we need positions in both strings. For knapsack, we need which items are available and remaining capacity. The state should be the smallest set of variables that uniquely identifies a subproblem. If you find yourself tracking information you could compute from the state, you're overcomplicating it.

A problem has optimal substructure when an optimal solution can be constructed from optimal solutions of its subproblems. This is essential for DP (and greedy) to work. For shortest path: the shortest path from A to C via B is the shortest A→B path plus the shortest B→C path. If a problem requires considering non-optimal subproblems to build an optimal solution, it lacks optimal substructure.

State explosion (high-dimensional DP) is a real problem. Techniques: 1) Remove unnecessary dimensions—do you really need that state variable? 2) Use space optimization when only previous states matter. 3) Consider memoization (top-down) to only compute needed states. 4) Look for alternative formulations. 5) For very large problems, consider approximate methods or specialized data structures. The key is getting correctness first—optimize only after the recurrence is verified.

If dp[i][j] depends on dp[i-1][j] (previous row) but you fill row i before row i-1, you'll read uninitialized values. The tabulation order ensures all required subproblems are computed first. For most standard recurrences, iterating dimensions in increasing order works. But some recurrences have unusual dependencies requiring careful ordering—always verify your recurrence's dependencies match your iteration order.