Dynamic Programming — Short Note

Definition

Optimization technique for problems with Optimal Substructure (optimal solution contains optimal solutions to subproblems) and Overlapping Subproblems (same subproblems recur many times). Solves each distinct subproblem once, stores result in table (memoization top-down or tabulation bottom-up).

Steps

1. Characterize optimal substructure, define DP state.
2. Write recurrence relating state to smaller states.
3. Compute table bottom-up (or memoized recursion), determine order.
4. Reconstruct optimal solution via parent pointers.

Key Properties vs Paradigms

• vs Divide&Conquer: D&C subproblems disjoint, DP overlapping.
• vs Greedy: Greedy picks local optimum once, DP explores all possibilities via table → guarantees global optimum when properties hold.

Classic Examples

• Fibonacci: naive $O(2^n)$ → DP $O(n)$
• 0/1 Knapsack: dp[i][w]=max(dp[i-1][w], dp[i-1][w-w_i]+p_i) → $O(nW)$ pseudo-polynomial
• Matrix Chain: $m[i][j]=\min_k m[i][k]+m[k+1][j]+p_{i-1}p_kp_j$ → $O(n^3)$
• LCS / Edit Distance: $O(mn)$
• Floyd-Warshall APSP: $O(V^3)$ DP over intermediate vertices
• Optimal BST: $O(n^3)$

Complexities

Time = #states × transition cost; Space = #states (often optimizable to less). Improvement over brute force often from exponential to polynomial/pseudo-polynomial.

When to Use

If problem has optimal substructure + overlapping → DP likely best exact polytime/pseudo-polytime. If greedy-choice holds, greedy faster.