Dynamic Programming

Dynamic programming is an algorithmic technique used to optimize recursive solutions by storing the results of overlapping subproblems. Instead of recomputing the same values repeatedly, dynamic programming solves each subproblem once and reuses the result.

DP is especially powerful for problems involving optimization, counting, and decision making, and it often turns exponential-time recursive solutions into efficient polynomial-time algorithms.

When Dynamic Programming Is Used

Dynamic programming is applicable when a problem has:

1. Overlapping subproblems The same subproblem appears multiple times

2. Optimal substructure An optimal solution can be built from optimal solutions of subproblems

If both properties are present, DP is likely a good fit.

Recursion vs Dynamic Programming

Dynamic programming is not a different algorithm - it is an optimization of recursion.

Two Approaches to DP

There are two main ways to implement dynamic programming:

1. Memoization (Top-Down)

• Start with recursion
• Store results of subproblems
• Avoid recomputation

solve(n):
    if cached[n]:
        return cached[n]
    cached[n] = solve(n-1) + solve(n-2)
    return cached[n]

2. Tabulation (Bottom-Up)

• Solve smaller subproblems first
• Build up the solution iteratively

dp[0] = ...
dp[1] = ...
for i in 2..n:
    dp[i] = dp[i-1] + dp[i-2]

DP Problem Patterns

Most DP problems fall into a few common patterns:

• Fibonacci-style (1D DP)
• Grid problems (2D DP)
• Knapsack problems
• Sequence alignment (LCS, LIS)
• Partition problems

Recognizing the pattern is often the hardest part.

Why DP Matters

Dynamic programming is crucial because:

• Many real-world problems are exponential without it
• It enables efficient optimization
• It appears frequently in interviews and contests
• It builds directly on recursion and backtracking

Once you understand DP, many “hard” problems become manageable.