Dynamic Programming

Dynamic Programming (DP) is an optimization technique that solves complex problems by breaking them into overlapping subproblems.

The Core Formula:

When to use DP:

• •Problem asks for COUNT of ways (paths, combinations)
• •Problem asks for MIN/MAX (cost, profit, length)
• •You see "take or skip", "include or exclude" decisions
• •Same subproblems are solved multiple times

Two Key Properties:

1. •Optimal Substructure: Optimal solution uses optimal sub-solutions
2. •Overlapping Subproblems: Same subproblem solved multiple times

Example - Fibonacci:

The DP Process:

1. •Write recursive solution (brute force)
2. •Add memoization (top-down DP)
3. •Convert to tabulation (bottom-up DP)
4. •Optimize space if possible

Use this framework to solve ANY DP problem:

Step 1: Define the State What information do I need to make a decision?

• •Usually: current index, remaining capacity, previous choice
• •State = parameters to your recursive function

Step 2: Define the Recurrence How does current state relate to smaller states?

• •What CHOICES do I have at this state?
• •Express dp[i] in terms of dp[smaller values]

Step 3: Identify Base Cases What are the simplest cases with obvious answers?

• •Empty array, index out of bounds, zero capacity

Step 4: Determine Computation Order Which direction to fill the table?

• •Dependencies must be computed first
• •Usually left->right, bottom->up

Step 5: Extract the Answer Where is the final answer?

• •Usually dp[n], dp[n-1], or dp[0]

Visualization:

Before writing any code, draw the decision tree. This is the most important step in DP!

What is a Decision Tree? A tree where each node represents a STATE, and each branch represents a CHOICE.

Example: Climbing Stairs (n=4)

Example: House Robber [2, 7, 9, 3]

Example: 0/1 Knapsack - items [(w=1,v=6), (w=2,v=10), (w=3,v=12)], capacity=5

How to Draw a Decision Tree:

1. •Identify the STATE - What changes as we make decisions?
2. •Identify CHOICES - What can we do at each state?
3. •Draw root - Start with the original problem
4. •Branch for each choice - Draw children for each option
5. •Continue until base case - Stop when answer is obvious
6. •Look for repeated subtrees - These are overlapping subproblems!

Key Insight:

The recurrence relation is the heart of any DP solution. Here's how to derive it systematically.

The 4-Question Method:

1. •What decision am I making?
2. •What are my choices?
3. •What happens after each choice?
4. •How do I combine the results?

Example 1: Climbing Stairs

Example 2: House Robber

Example 3: Coin Change (Minimum coins)

Example 4: Longest Common Subsequence

Common Combination Patterns:

Writing the Recurrence - Template:

Let's transform a problem through ALL FOUR stages using House Robber as our example.

Problem: Given array [2, 7, 9, 3, 1], find max money without robbing adjacent houses.

Answer: 12 (rob houses with values 2, 9, 1)

STAGE 1: PURE RECURSION (Brute Force)

Decision Tree for [2, 7, 9, 3, 1]:

STAGE 2: MEMOIZATION (Top-Down DP)

Execution trace with memo:

STAGE 3: TABULATION (Bottom-Up DP)

Filling the DP table:

STAGE 4: SPACE OPTIMIZATION

Trace with 2 variables:

Summary: The 4 Stages

Two ways to implement DP:

Memoization (Top-Down)

• •Start from the main problem, recurse down
• •Cache results as you go
• •More intuitive - matches recursive thinking
• •Only computes needed subproblems

Tabulation (Bottom-Up)

• •Start from base cases, build up
• •Fill a table iteratively
• •Usually faster (no recursion overhead)
• •Easier to optimize space

Comparison:

When to use which:

• •Start with memoization (easier to think)
• •Convert to tabulation for performance
• •Use tabulation when you need space optimization

Conversion Process:

Problems where state depends on previous elements in a sequence.

Common Patterns:

1. •House Robber - Take or skip decision

1. •Coin Change - Minimize count

1. •Word Break - Can we segment?

Visualization - House Robber:

Problems with two dimensions: grids, two strings, or two arrays.

Pattern 1: Grid Paths

Pattern 2: Two Strings (LCS, Edit Distance)

Visualization - Unique Paths:

Visualization - LCS (Longest Common Subsequence):

Classic DP pattern: Given items with weights/values, maximize value within capacity.

The Pattern:

• •For each item: TAKE it or SKIP it
• •State: (current item index, remaining capacity)
• •Decision: Include this item or not?

Recurrence:

Visualization:

Related Problems:

• •Partition Equal Subset Sum (can we split into equal halves?)
• •Target Sum (count ways to reach target)
• •Coin Change (unbounded - can reuse items)

Find the longest subsequence where elements are in increasing order.

Problem: [10, 9, 2, 5, 3, 7, 101, 18] -> LIS = [2, 3, 7, 101] or [2, 3, 7, 18], length = 4

O(n²) DP Solution:

Visualization:

O(n log n) Optimization: Maintain a sorted array of smallest tail elements. Use binary search to find position.

Common patterns for string DP problems.

Pattern 1: Single String

• •Palindrome problems
• •dp[i][j] = property of substring s[i..j]

Pattern 2: Two Strings

• •LCS, Edit Distance, Interleaving
• •dp[i][j] = property using s1[0..i] and s2[0..j]

Longest Palindromic Substring:

Visualization:

Quick reference for identifying DP problem types:

By Problem Type:

Space Optimization Rules:

Common Mistakes:

• •Wrong base case initialization
• •Wrong iteration direction (must compute dependencies first)
• •Off-by-one errors in indices
• •Forgetting to handle edge cases (empty input)

DP vs Greedy: