Home/Learn/DSA/Dynamic Programming

Dynamic Programming

Advanced

Break problems into overlapping subproblems. Master the 5 key DP patterns that cover 80% of interview questions.

Think of it this way

Think of climbing a staircase and counting how many ways you can reach each step. To reach step 10, you either came from step 9 or step 8. If you already wrote down the answer for step 9 and step 8, you get step 10 instantly without recounting. DP is simply writing down answers to small problems so you never solve the same sub-problem twice.

In code, it looks like thisJava
// Naive recursion — recalculates the same values exponentially
int fib(int n) { return n <= 1 ? n : fib(n-1) + fib(n-2); } // O(2^n) ✗

// DP tabulation — fill a table bottom-up — O(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]; // reuse already-computed answers

Overview

Dynamic Programming (DP) solves problems by breaking them into overlapping subproblems, storing results to avoid recomputation (memoization or tabulation). The key insight is recognizing that a problem has optimal substructure (optimal solution contains optimal solutions to subproblems) and overlapping subproblems (same subproblems are solved repeatedly). DP is arguably the hardest topic in interviews, but 80% of DP problems fall into 5 patterns.

Time & Space Complexity

Operation Time Space
Fibonacci (naive recursion)O(2^n)O(n)
Fibonacci (memoization)O(n)O(n)
Fibonacci (tabulation)O(n)O(1)
0/1 KnapsackO(n * W)O(n * W)
LCS / Edit DistanceO(m * n)O(m * n)

Java Implementation

Java
public class DynamicProgramming {

    // Coin change — minimum coins to make amount, O(n * amount)
    public static int coinChange(int[] coins, int amount) {
        int[] dp = new int[amount + 1];
        java.util.Arrays.fill(dp, amount + 1); // "infinity"
        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];
    }

    // Longest Common Subsequence — O(m * n)
    public static 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];
    }

    // 0/1 Knapsack — O(n * W)
    public static int knapsack(int[] weights, int[] values, int W) {
        int n = weights.length;
        int[][] dp = new int[n + 1][W + 1];
        for (int i = 1; i <= n; i++) {
            for (int w = 0; w <= W; w++) {
                dp[i][w] = dp[i-1][w]; // skip item
                if (weights[i-1] <= w) {
                    dp[i][w] = Math.max(dp[i][w], values[i-1] + dp[i-1][w - weights[i-1]]);
                }
            }
        }
        return dp[n][W];
    }

    // Longest Increasing Subsequence — O(n log n) with patience sorting
    public static int lis(int[] nums) {
        java.util.List<Integer> tails = new java.util.ArrayList<>();
        for (int num : nums) {
            int lo = 0, hi = tails.size();
            while (lo < hi) {
                int mid = (lo + hi) / 2;
                if (tails.get(mid) < num) lo = mid + 1; else hi = mid;
            }
            if (lo == tails.size()) tails.add(num);
            else tails.set(lo, num);
        }
        return tails.size();
    }
}

Key Points to Remember

  • Pattern 1 — Linear DP: each cell depends on previous cells (Fibonacci, climbing stairs, house robber)
    dp[i] = Math.max(dp[i-1], dp[i-2] + nums[i]); // house robber: skip or take
  • Pattern 2 — Grid DP: move through a 2D grid, each cell depends on neighbours above/left
    dp[i][j] = Math.min(dp[i-1][j], dp[i][j-1]) + grid[i][j]; // minimum path sum
  • Pattern 3 — Interval DP: solve for ranges, combine sub-range answers (burst balloons, matrix chain)
  • Pattern 4 — Knapsack: pick items with weight/value constraints (coin change, subset sum)
    // Coin change: for each amount, try every coin
for (int coin : coins)
    if (coin <= i) dp[i] = Math.min(dp[i], dp[i - coin] + 1);
  • Pattern 5 — String DP: compare two strings character by character (LCS, edit distance)
    // LCS: if chars match, extend; otherwise take the best of skip-left or skip-right
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]);

Interview Questions

Sign in to ask Aria
1

Climbing stairs / Fibonacci variants

EasyAmazonSolve it
2

Coin change — minimum number of coins

MediumGoogleSolve it
3

Longest Increasing Subsequence

MediumMicrosoftSolve it
4

Edit distance between two strings

HardGoogleSolve it
5

Partition equal subset sum (NP-hard → DP)

MediumFacebookSolve it

Ask Aria about Dynamic Programming

Your personal AI tutor — ask anything about this concept

Previous
Searching Algorithms
Next
Hashing