Dynamic Programming Pattern

Overview

Break complex problems into overlapping subproblems, solve each once, and store results for reuse. Choose between top-down (memoization) and bottom-up (tabulation) approaches.

When to Use

• Optimization problems (min/max)
• Counting problems (number of ways)
• Overlapping subproblems
• Optimal substructure (optimal solution contains optimal sub-solutions)
• Decision problems (is it possible?)

Template Code

1D DP - Climbing Stairs

// Bottom-up
public int climbStairs(int n) {
    if (n <= 2) return n;

    int[] dp = new int[n + 1];
    dp[1] = 1;
    dp[2] = 2;

    for (int i = 3; i <= n; i++) {
        dp[i] = dp[i - 1] + dp[i - 2];
    }

    return dp[n];
}

// Space optimized
public int climbStairsOptimized(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;
}

House Robber (Cannot Rob Adjacent)

public int rob(int[] nums) {
    if (nums.length == 1) return nums[0];

    int prev2 = nums[0];
    int prev1 = Math.max(nums[0], nums[1]);

    for (int i = 2; i < nums.length; i++) {
        int curr = Math.max(prev1, prev2 + nums[i]);
        prev2 = prev1;
        prev1 = curr;
    }

    return prev1;
}

Coin Change (Minimum Coins)

public int coinChange(int[] coins, int amount) {
    int[] dp = new int[amount + 1];
    Arrays.fill(dp, amount + 1);  // Impossible value
    dp[0] = 0;

    for (int i = 1; i <= amount; i++) {
        for (int coin : coins) {
            if (coin <= i) {
                dp[i] = Math.min(dp[i], dp[i - coin] + 1);
            }
        }
    }

    return dp[amount] > amount ? -1 : dp[amount];
}

Coin Change II (Number of Ways)

public int change(int amount, int[] coins) {
    int[] dp = new int[amount + 1];
    dp[0] = 1;  // One way to make 0

    for (int coin : coins) {
        for (int i = coin; i <= amount; i++) {
            dp[i] += dp[i - coin];
        }
    }

    return dp[amount];
}

Longest Increasing Subsequence

// O(n²) DP solution
public int lengthOfLIS(int[] nums) {
    int[] dp = new int[nums.length];
    Arrays.fill(dp, 1);  // Each element is LIS of length 1

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

    return maxLen;
}

// O(n log n) Binary search solution
public int lengthOfLISOptimized(int[] nums) {
    List<Integer> tails = new ArrayList<>();

    for (int num : nums) {
        int pos = Collections.binarySearch(tails, num);
        if (pos < 0) pos = -(pos + 1);

        if (pos == tails.size()) {
            tails.add(num);
        } else {
            tails.set(pos, num);
        }
    }

    return tails.size();
}

2D DP - Unique Paths

public int uniquePaths(int m, int n) {
    int[][] dp = new int[m][n];

    // First row and column have only one path
    for (int i = 0; i < m; i++) dp[i][0] = 1;
    for (int j = 0; j < n; j++) dp[0][j] = 1;

    for (int i = 1; i < m; i++) {
        for (int j = 1; j < n; j++) {
            dp[i][j] = dp[i-1][j] + dp[i][j-1];
        }
    }

    return dp[m-1][n-1];
}

Longest Common Subsequence

public 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];
}

Edit Distance

public int minDistance(String word1, String word2) {
    int m = word1.length(), n = word2.length();
    int[][] dp = new int[m + 1][n + 1];

    // Base cases
    for (int i = 0; i <= m; i++) dp[i][0] = i;  // Delete all
    for (int j = 0; j <= n; j++) dp[0][j] = j;  // Insert all

    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= n; j++) {
            if (word1.charAt(i-1) == word2.charAt(j-1)) {
                dp[i][j] = dp[i-1][j-1];  // No operation needed
            } else {
                dp[i][j] = 1 + Math.min(
                    dp[i-1][j-1],  // Replace
                    Math.min(dp[i-1][j], dp[i][j-1])  // Delete or Insert
                );
            }
        }
    }

    return dp[m][n];
}

0/1 Knapsack

public int knapsack(int[] weights, int[] values, int capacity) {
    int n = weights.length;
    int[][] dp = new int[n + 1][capacity + 1];

    for (int i = 1; i <= n; i++) {
        for (int w = 0; w <= capacity; w++) {
            // Don't take item i
            dp[i][w] = dp[i-1][w];

            // Take item i (if it fits)
            if (weights[i-1] <= w) {
                dp[i][w] = Math.max(dp[i][w],
                    dp[i-1][w - weights[i-1]] + values[i-1]);
            }
        }
    }

    return dp[n][capacity];
}

Longest Palindromic Substring

public String longestPalindrome(String s) {
    int n = s.length();
    boolean[][] dp = new boolean[n][n];
    int start = 0, maxLen = 1;

    // All single chars are palindromes
    for (int i = 0; i < n; i++) {
        dp[i][i] = true;
    }

    // Check substrings of length 2
    for (int i = 0; i < n - 1; i++) {
        if (s.charAt(i) == s.charAt(i + 1)) {
            dp[i][i + 1] = true;
            start = i;
            maxLen = 2;
        }
    }

    // Check substrings of length 3+
    for (int len = 3; len <= n; len++) {
        for (int i = 0; i <= n - len; i++) {
            int j = i + len - 1;

            if (s.charAt(i) == s.charAt(j) && dp[i + 1][j - 1]) {
                dp[i][j] = true;
                start = i;
                maxLen = len;
            }
        }
    }

    return s.substring(start, start + maxLen);
}

Word Break

public boolean wordBreak(String s, List<String> wordDict) {
    Set<String> wordSet = new HashSet<>(wordDict);
    boolean[] dp = new boolean[s.length() + 1];
    dp[0] = true;  // Empty string

    for (int i = 1; i <= s.length(); i++) {
        for (int j = 0; j < i; j++) {
            if (dp[j] && wordSet.contains(s.substring(j, i))) {
                dp[i] = true;
                break;
            }
        }
    }

    return dp[s.length()];
}

Maximum Subarray (Kadane's Algorithm)

public int maxSubArray(int[] nums) {
    int maxSum = nums[0];
    int currentSum = nums[0];

    for (int i = 1; i < nums.length; i++) {
        currentSum = Math.max(nums[i], currentSum + nums[i]);
        maxSum = Math.max(maxSum, currentSum);
    }

    return maxSum;
}

Time & Space Complexity

Problem	Time	Space
Climbing stairs	O(n)	O(1)
House robber	O(n)	O(1)
Coin change	O(n × amount)	O(amount)
LIS	O(n²) or O(n log n)	O(n)
Unique paths	O(m × n)	O(n)
LCS	O(m × n)	O(m × n)
Edit distance	O(m × n)	O(m × n)
Knapsack	O(n × W)	O(n × W)

Common Interview Questions

1. Climbing Stairs - Ways to reach top
2. House Robber I, II - Max robbery without adjacent
3. Coin Change - Min coins for amount
4. Coin Change II - Number of ways
5. Longest Increasing Subsequence - LIS length
6. Unique Paths - Grid paths
7. Minimum Path Sum - Grid min cost
8. Longest Common Subsequence - LCS
9. Edit Distance - Min operations
10. Word Break - Can segment into words
11. Maximum Subarray - Kadane's algorithm
12. Longest Palindromic Substring - Expand around center or DP
13. Decode Ways - Count decodings
14. 0/1 Knapsack - Max value with capacity
15. Partition Equal Subset Sum - Can partition into equal halves
16. Target Sum - Ways to reach target with +/-

Tips & Tricks

• Identify the state: what variables define a subproblem?
• Define recurrence relation clearly
• Handle base cases
• Consider space optimization (often only need previous row)
• Top-down is easier to think about; bottom-up is usually faster
• Draw the DP table for 2D problems to visualize
• For string problems, think about comparing characters