Dynamic Programming

DP solves problems by breaking them into overlapping subproblems, solving each subproblem once, and storing the result to avoid recomputation.

• Replaces exponential brute-force recursion with polynomial time by caching subproblem results (memoization) or filling a table iteratively (tabulation)
• Two styles: top-down memoization adds caching to a recursive solution, bottom-up tabulation fills a dp array from base cases upward
• Reach for it when the problem asks for count of ways, optimal value, or feasibility, and each choice affects what future choices are available

Quick Revision - Must Do Problems

If short on time, solve only these. They cover ~90% of DP patterns.

Practice Tips

How to Identify a DP Problem

• Problem asks for "number of ways", "minimum cost", "maximum value", or "is it possible"
• Choices at one step affect or constrain future choices (optimal substructure)
• Brute force is exponential but the same subproblems recur (overlapping subproblems)
• Keywords: "count", "minimum", "maximum", "can you reach", "how many distinct"

DP vs. Other Techniques

Interview Approach

1. Define state: what does dp[i] or dp[i][j] represent in plain English?
2. Write the recurrence: how does dp[i] depend on smaller subproblems?
3. Set base cases: what are dp[0] and dp[1] (or dp[0][j] and dp[i][0])?
4. Choose fill order: left-to-right (forward) or right-to-left (backward for 0/1 knapsack)?
5. Identify the answer: is it dp[n], dp[n-1], max over all dp[i], or something else?

Formula Cheatsheet

5 Main Patterns

Pattern 1: Linear 1D DP

Copy// dp[i] depends on 1 or 2 previous states
int[] dp = new int[n + 1];
dp[0] = BASE_0;
dp[1] = BASE_1;
for (int i = 2; i <= n; i++) {
    dp[i] = combine(dp[i-1], dp[i-2]);
}

Pattern 2: 2D Grid / String DP

Copy// dp[i][j] depends on dp[i-1][j], dp[i][j-1], or dp[i-1][j-1]
int[][] dp = new int[m + 1][n + 1];
for (int i = 1; i <= m; i++) {
    for (int j = 1; j <= n; j++) {
        if (match(i, j)) {
            dp[i][j] = dp[i-1][j-1] + 1;
        }
        else {
            dp[i][j] = Math.max(dp[i-1][j], dp[i][j-1]);
        }
    }
}

Pattern 3: 0/1 Knapsack (Subset DP)

Copy// Each item used at most once — iterate BACKWARD to prevent reuse
boolean[] dp = new boolean[target + 1];
dp[0] = true;
for (int num : nums) {
    for (int i = target; i >= num; i--) {  // backward = no reuse
        dp[i] = dp[i] || dp[i - num];
    }
}

Pattern 4: Unbounded Knapsack

Copy// Items can be reused — iterate FORWARD (inner loop)
int[] dp = new int[amount + 1];
Arrays.fill(dp, amount + 1);    // sentinel for "unreachable"
dp[0] = 0;
for (int i = 1; i <= amount; i++) {
    for (int coin : coins) {
        if (i >= coin) {
            dp[i] = Math.min(dp[i], dp[i - coin] + 1);
        }
    }
}

Pattern 5: Sequence DP (LIS-style)

Copy// dp[i] = best result of sequence ending at index i
// Must look back at all j < i
int[] dp = new int[n];
Arrays.fill(dp, 1);             // every element is length-1 sequence
for (int i = 1; i < n; i++) {
    for (int j = 0; j < i; j++) {
        if (nums[j] < nums[i]) {
            dp[i] = Math.max(dp[i], dp[j] + 1);
        }
    }
}
int ans = 0;
for (int val : dp) {
    ans = Math.max(ans, val);
}

General Templates

Space-Optimized 1D DP

Copy// When dp[i] only needs dp[i-1] and dp[i-2]
int prev2 = BASE_0, prev1 = BASE_1;
for (int i = 2; i <= n; i++) {
    int curr = combine(prev1, prev2);
    prev2 = prev1;
    prev1 = curr;
}
return prev1;

0/1 Knapsack (Minimize)

Copy// dp[i] = min cost to achieve capacity i
int[] dp = new int[capacity + 1];
Arrays.fill(dp, Integer.MAX_VALUE);
dp[0] = 0;
for (int item : items) {
    for (int i = capacity; i >= item; i--) {   // backward
        if (dp[i - item] != Integer.MAX_VALUE) {
            dp[i] = Math.min(dp[i], dp[i - item] + cost);
        }
    }
}

Problem 1: Climbing Stairs ⭐ MUST DO [B75-70]

You can climb 1 or 2 steps at a time. Return the number of distinct ways to reach step n.

Example:

CopyInput:  n = 2  →  2   (1+1 or 2)
Input:  n = 3  →  3   (1+1+1, 1+2, 2+1)
Input:  n = 5  →  8

Key Insight:

• To reach stair i, you either came from stair i-1 (took 1 step) or stair i-2 (took 2 steps). So the total ways = dp[i-1] + dp[i-2]. This is the Fibonacci sequence.
• Formula: dp[i] = dp[i-1] + dp[i-2], base cases dp[0]=1, dp[1]=1

Solution:

Copypublic int climbStairs(int n) {
    if (n <= 2) {
        return n;
    }
    int prev2 = 1, prev1 = 2;
    for (int i = 3; i <= n; i++) {
        int curr = prev1 + prev2;
        prev2 = prev1;
        prev1 = curr;
    }
    return prev1;
}

Complexity:

Variants — same pattern, different formula:

Allow 3 steps (1, 2, or 3):

Copy// dp[i] = dp[i-1] + dp[i-2] + dp[i-3]
// base: dp[0]=1, dp[1]=1, dp[2]=2
// climbStairs(7) = 44
dp[i] = dp[i-1] + dp[i-2] + dp[i-3];

Minimum cost climbing stairs (LC #746): Each stair has a cost. You can start from index 0 or 1. Reach the top (index n) with minimum cost.

Copy// dp[i] = min cost to reach position i
// dp[i] = min(dp[i-1] + cost[i-1], dp[i-2] + cost[i-2])
// base: dp[0]=0, dp[1]=0  (free to start at either)
// cost=[1,100,1,1,100,1] → answer: 4
public int minCostClimbingStairs(int[] cost) {
    int n = cost.length;
    int[] dp = new int[n + 1];
    for (int i = 2; i <= n; i++) {
        dp[i] = Math.min(dp[i-1] + cost[i-1], dp[i-2] + cost[i-2]);
    }
    return dp[n];
}

Problem 2: Jump Game ⭐ MUST DO [B75-55]

Given an array where nums[i] is your max jump length from index i, return true if you can reach the last index.

Example:

CopyInput:  [2, 3, 1, 1, 4]  →  true   (0→1→4)
Input:  [3, 2, 1, 0, 4]  →  false  (always land on index 3 where nums[3]=0)

Key Insight:

• Track the farthest index reachable at each step. If the current index i exceeds maxReach, you are stuck — you cannot reach index i or anything beyond it.

Solution:

Copypublic boolean canJump(int[] nums) {
    int maxReach = 0;
    for (int i = 0; i < nums.length; i++) {
        if (i > maxReach) {
            return false;         // can't reach index i
        }
        maxReach = Math.max(maxReach, i + nums[i]);
    }
    return true;
}

Complexity:

Problem 3: House Robber ⭐ MUST DO [B75-198]

Rob houses in a row without robbing two adjacent ones. Return the maximum amount you can rob.

Example:

CopyInput:  [1, 2, 3, 1]    →  4   (rob houses 1 and 3)
Input:  [2, 7, 9, 3, 1] →  12  (rob houses 1, 3, 5)

Key Insight:

• At each house, decide: skip it (take the previous max) or rob it (take prev-prev max + current value). The max of those two choices is the best you can do through house i.

Solution:

Copypublic int rob(int[] nums) {
    int prev2 = 0, prev1 = 0;
    for (int num : nums) {
        int curr = Math.max(prev1, prev2 + num);
        prev2 = prev1;
        prev1 = curr;
    }
    return prev1;
}

Complexity:

Problem 4: House Robber II ⭐ MUST DO [B75-213]

Same as House Robber but houses are arranged in a circle — the first and last are adjacent. Return the maximum amount.

Example:

CopyInput:  [2, 3, 2]    →  3   (can't rob both house 1 and 3)
Input:  [1, 2, 3, 1] →  4

Key Insight:

• You cannot rob both the first and last house. Run the linear House Robber twice: once on nums[0..n-2] (exclude last), once on nums[1..n-1] (exclude first). Take the max.

Solution:

Copypublic int rob(int[] nums) {
    int n = nums.length;
    if (n == 1) {
        return nums[0];
    }
    return Math.max(robRange(nums, 0, n - 2), robRange(nums, 1, n - 1));
}

private int robRange(int[] nums, int start, int end) {
    int prev2 = 0, prev1 = 0;
    for (int i = start; i <= end; i++) {
        int curr = Math.max(prev1, prev2 + nums[i]);
        prev2 = prev1;
        prev1 = curr;
    }
    return prev1;
}

Complexity:

Problem 5: Unique Paths ⭐ MUST DO [B75-62]

Count all unique paths from top-left to bottom-right of an m × n grid, moving only right or down.

Example:

CopyInput:  m = 3, n = 7  →  28
Input:  m = 3, n = 2  →  3

Key Insight:

• dp[i][j] = dp[i-1][j] + dp[i][j-1]: paths to any cell equal the sum of paths from the cell above and the cell to the left. The entire first row and first column are 1 (only one way to reach them).

Solution:

Copypublic int uniquePaths(int m, int n) {
    int[] dp = new int[n];
    Arrays.fill(dp, 1);                 // top row: 1 path to each cell
    for (int i = 1; i < m; i++) {
        for (int j = 1; j < n; j++) {
            dp[j] += dp[j - 1];         // above (dp[j]) + left (dp[j-1])
        }
    }
    return dp[n - 1];
}

Complexity:

Problem 6: Coin Change ⭐ MUST DO [B75-322]

Return the fewest coins needed to make up the amount. Coins can be used any number of times. Return -1 if impossible.

Example:

CopyInput:  coins = [1, 5, 11],  amount = 15  →  3   (5+5+5)
Input:  coins = [2],          amount = 3   →  -1

Key Insight:

• Unbounded knapsack: coins are reusable. Fill dp left to right. dp[i] = minimum coins to make amount i. Try every coin at each amount — if dp[i - coin] is reachable, dp[i] might be updated.

Solution:

Copypublic int coinChange(int[] coins, int amount) {
    int[] dp = new int[amount + 1];
    Arrays.fill(dp, amount + 1);    // sentinel for "unreachable"
    dp[0] = 0;
    for (int i = 1; i <= amount; i++) {
        for (int coin : coins) {
            if (i >= coin) {
                dp[i] = Math.min(dp[i], dp[i - coin] + 1);
            }
        }
    }
    return dp[amount] > amount ? -1 : dp[amount];
}

Complexity:

Problem 7: Decode Ways ⭐ MUST DO [B75-91]

A string of digits can be decoded as letters (1→A through 26→Z). Return the number of ways to decode the string.

Example:

CopyInput:  "12"   →  2   ("AB" or "L")
Input:  "226"  →  3   ("BZ", "VF", "BBF")
Input:  "06"   →  0   (leading zero — invalid)

Key Insight:

• dp[i] = number of ways to decode s[0..i-1]. At each position, check two cases: the single digit s[i-1] (valid if not '0'), and the two-digit number s[i-2..i-1] (valid if in range 10–26). Add dp[i-1] or dp[i-2] accordingly.

Solution:

Copypublic int numDecodings(String s) {
    int n = s.length();
    int[] dp = new int[n + 1];
    dp[0] = 1;                                  // empty prefix: 1 way
    dp[1] = s.charAt(0) == '0' ? 0 : 1;

    for (int i = 2; i <= n; i++) {
        int oneDigit = Integer.parseInt(s.substring(i - 1, i));
        int twoDigit = Integer.parseInt(s.substring(i - 2, i));
        if (oneDigit >= 1) {
            dp[i] += dp[i - 1];                 // valid single digit
        }
        if (twoDigit >= 10 && twoDigit <= 26) {
            dp[i] += dp[i - 2];                 // valid two digit
        }
    }
    return dp[n];
}

Complexity:

Problem 8: Word Break ⭐ MUST DO [B75-139]

Return true if string s can be segmented into a space-separated sequence of dictionary words.

Example:

CopyInput:  s = "leetcode",   wordDict = ["leet","code"]                →  true
Input:  s = "catsandog",  wordDict = ["cats","dog","sand","and","cat"]  →  false

Key Insight:

• dp[i] = true if s[0..i-1] can be fully segmented. For each end position i, scan all start positions j: if dp[j] is true and s[j..i-1] is in the dictionary, then dp[i] = true.

Solution:

Copypublic boolean wordBreak(String s, List<String> wordDict) {
    Set<String> dict = new HashSet<>(wordDict);
    boolean[] dp = new boolean[s.length() + 1];
    dp[0] = true;
    for (int i = 1; i <= s.length(); i++) {
        for (int j = 0; j < i; j++) {
            if (dp[j] && dict.contains(s.substring(j, i))) {
                dp[i] = true;
                break;
            }
        }
    }
    return dp[s.length()];
}

Complexity:

Problem 9: Partition Equal Subset Sum ⭐ MUST DO

Determine if an array can be partitioned into two subsets with equal sum.

Example:

CopyInput:  [1, 5, 11, 5]  →  true   ({1,5,5} and {11})
Input:  [1, 2, 3, 5]   →  false

Key Insight:

• Equivalent to: can we find a subset that sums to total/2? If total is odd, immediately false.
• Use 0/1 knapsack on a boolean dp array. Iterate backward so each element is considered at most once.

Solution:

Copypublic boolean canPartition(int[] nums) {
    int total = 0;
    for (int n : nums) {
        total += n;
    }
    if (total % 2 != 0) {
        return false;
    }

    int target = total / 2;
    boolean[] dp = new boolean[target + 1];
    dp[0] = true;

    for (int num : nums) {
        for (int i = target; i >= num; i--) {   // backward = no reuse
            dp[i] = dp[i] || dp[i - num];
        }
    }
    return dp[target];
}

Complexity:

Problem 10: Longest Increasing Subsequence ⭐ MUST DO [B75-300]

Return the length of the longest strictly increasing subsequence.

Example:

CopyInput:  [10, 9, 2, 5, 3, 7, 101, 18]  →  4   ([2, 3, 7, 101])
Input:  [0, 1, 0, 3, 2, 3]            →  4   ([0, 1, 2, 3])

Key Insight:

• dp[i] = length of the LIS ending exactly at index i. For each i, scan all j < i: if nums[j] < nums[i], dp[i] = max(dp[i], dp[j] + 1).
• The answer is the max over all dp[i] — the LIS can end at any index, not just the last.

Solution:

Copypublic int lengthOfLIS(int[] nums) {
    int n = nums.length;
    int[] dp = new int[n];
    Arrays.fill(dp, 1);             // every element is a length-1 subsequence

    for (int i = 1; i < n; i++) {
        for (int j = 0; j < i; j++) {
            if (nums[j] < nums[i]) {
                dp[i] = Math.max(dp[i], dp[j] + 1);
            }
        }
    }

    int max = 0;
    for (int val : dp) {
        max = Math.max(max, val);
    }
    return max;
}

Complexity:

Problem 11: Combination Sum IV ⭐ MUST DO [B75-377]

Return the number of ordered sequences (order matters) that add up to target. Numbers can be reused.

Example:

CopyInput:  nums = [1, 2, 3],  target = 4  →  7
   (1+1+1+1, 1+1+2, 1+2+1, 1+3, 2+1+1, 2+2, 3+1)

Key Insight:

• Order matters, so this counts permutations, not combinations. The key is to loop over target values in the outer loop and items in the inner loop — this lets you count all orderings.
• dp[i] = number of ordered sequences summing to i.

Solution:

Copypublic int combinationSum4(int[] nums, int target) {
    int[] dp = new int[target + 1];
    dp[0] = 1;                          // one way to make 0: empty sequence
    for (int i = 1; i <= target; i++) {
        for (int num : nums) {
            if (i >= num) {
                dp[i] += dp[i - num];
            }
        }
    }
    return dp[target];
}

Complexity:

Problem 12: Longest Common Subsequence ⭐ MUST DO [B75-1143]

Return the length of the longest common subsequence of two strings.

Example:

CopyInput:  text1 = "abcde",  text2 = "ace"  →  3   ("ace")
Input:  text1 = "abc",    text2 = "abc"  →  3
Input:  text1 = "abc",    text2 = "def"  →  0

Key Insight:

• dp[i][j] = LCS length of text1[0..i-1] and text2[0..j-1]. When characters match, extend the LCS from the diagonal. When they don't, take the best of skipping one character from either string.

Solution:

Copypublic int longestCommonSubsequence(String text1, String text2) {
    int m = text1.length(), n = text2.length();
    int[][] dp = new int[m + 1][n + 1];
    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= n; j++) {
            if (text1.charAt(i - 1) == text2.charAt(j - 1)) {
                dp[i][j] = dp[i-1][j-1] + 1;
            }
            else {
                dp[i][j] = Math.max(dp[i-1][j], dp[i][j-1]);
            }
        }
    }
    return dp[m][n];
}

Complexity:

Quick Reference Table

When to Use Each Pattern

Linear 1D DP

• Problem involves a sequence and the current state depends on 1–2 previous states
• Classic signals: "can't pick adjacent", "ways to reach step n", "count valid decodings"
• Space-optimize by keeping only prev1 and prev2 when the full array isn't needed

2D Grid / String DP

• Grid path problems where you move right or down (Unique Paths, Min Path Sum)
• Two-string matching problems (LCS, edit distance, longest palindromic subsequence)
• dp dimensions = lengths of the two inputs; extra row/col for the empty-string base case

0/1 Knapsack (Subset DP)

• Selecting items with a budget where each item is used at most once
• Iterate the capacity dimension backward — this prevents reusing the same item
• Boolean variant: "can we achieve exactly X sum?"; integer variant: min/max value at capacity X

Unbounded Knapsack

• Items are reusable (coins, tiles, numbers from an array)
• Iterate the capacity dimension forward — reuse is allowed
• Outer loop on capacity/target, inner loop on items (for min/max problems)
• For count-of-permutations: outer loop on target, inner loop on items

Sequence DP (LIS-style)

• Finding the optimal subsequence in an array — length, count, or value
• dp[i] = best result of a sequence ending at index i, not best up to i
• Answer is max over all dp[i], not dp[n-1], since the optimal subsequence can end anywhere

Common Mistakes to Avoid

General DP Mistakes

1. Wrong state definition — dp[i] must have a clear, precise meaning; if you can't state it in plain English, the recurrence will be wrong
2. Wrong answer location — the answer is not always dp[n]; for LIS it is the max over all dp[i]; for grid DP it is dp[m-1][n-1]
3. Off-by-one in array sizing — for string/array inputs, use dp[n+1] with dp[0] as the empty-prefix base case

1D DP Mistakes

4. Wrong base cases — Climbing Stairs needs dp[1]=1 and dp[2]=2; Decode Ways needs dp[0]=1 (empty string); always verify the first two values manually
5. Decode Ways: not handling '0' — a single '0' cannot be decoded; forgetting this gives wrong answers for inputs like "10" or "30"

Knapsack Mistakes

6. Forward instead of backward in 0/1 knapsack — iterating forward allows using the same item multiple times; always iterate backward for 0/1 (each item once)
7. Forgetting the unreachable sentinel — in Coin Change, initialize dp with amount + 1 (not 0); initializing with 0 makes every amount appear reachable

2D DP Mistakes

8. Skipping base row/column initialization — for grid DP, the first row and column must be set before the main fill loop; they have only one path each

Sequence DP Mistakes

9. Returning dp[n-1] for LIS — the LIS can end at any index; return max over all dp[i], not dp[n-1]
10. Wrong loop order for Combination Sum IV — order matters (permutations); the outer loop must be over target values, not items; items-outer would count combinations instead