Dynamic Programming

DP solves problems by breaking them into overlapping subproblems with optimal substructure. Two approaches: top-down (recursion + memoization) and bottom-up (tabulation). Steps: define state, write recurrence, identify base cases, optimize space if possible. Common patterns: 1D DP (climbing stairs), 2D DP (grid paths), knapsack, LCS, LIS.

Key Concepts

Deep Dive: Top-Down vs Bottom-Up

Problem: Fibonacci

Top-Down (Memoization):

int[] memo;
public int fib(int n) {
    memo = new int[n + 1];
    Arrays.fill(memo, -1);
    return solve(n);
}
private int solve(int n) {
    if (n <= 1) return n;
    if (memo[n] != -1) return memo[n];
    return memo[n] = solve(n - 1) + solve(n - 2);
}

Bottom-Up (Tabulation):

public int fib(int n) {
    if (n <= 1) return n;
    int[] dp = new int[n + 1];
    dp[0] = 0; dp[1] = 1;
    for (int i = 2; i <= n; i++) dp[i] = dp[i-1] + dp[i-2];
    return dp[n];
}

Space-Optimized:

public int fib(int n) {
    if (n <= 1) return n;
    int prev2 = 0, prev1 = 1;
    for (int i = 2; i <= n; i++) {
        int curr = prev1 + prev2;
        prev2 = prev1;
        prev1 = curr;
    }
    return prev1;
}

Deep Dive: Classic DP Patterns

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++) {
            dp[i][w] = dp[i-1][w];  // Don't take
            if (weights[i-1] <= w) {
                dp[i][w] = Math.max(dp[i][w],
                    dp[i-1][w - weights[i-1]] + values[i-1]);  // Take
            }
        }
    }
    return dp[n][capacity];
}

Longest Common Subsequence (LCS):

public int lcs(String s1, String s2) {
    int m = s1.length(), n = s2.length();
    int[][] dp = new int[m + 1][n + 1];
    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= n; j++) {
            if (s1.charAt(i-1) == s2.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];
}

Longest Increasing Subsequence (LIS):

// O(n log n) using patience sorting
public int lis(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();
}

Deep Dive: DP on Grid

Unique Paths:

public int uniquePaths(int m, int n) {
    int[][] dp = new int[m][n];
    Arrays.fill(dp[0], 1);
    for (int i = 0; i < m; i++) dp[i][0] = 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];
}

Common Interview Questions

• Climbing Stairs
• Coin Change (min coins)
• Longest Common Subsequence
• Longest Increasing Subsequence
• 0/1 Knapsack
• House Robber
• Word Break
• Edit Distance
• Unique Paths
• Palindrome Partitioning