DYNAMIC
PROGRAMMING CHEATSHEET.

What is DP?

Dynamic Programming is a method for solving complex problems by breaking them down into simpler subproblems, solving each subproblem once, and storing the results to avoid redundant computations.

Key Characteristics

• Optimal Substructure – optimal solution can be constructed from optimal solutions of subproblems
• Overlapping Subproblems – same subproblems appear multiple times
• Memorisation – store results of subproblems to avoid recomputation

When to Use DP

Two DP Approaches

DP Problem Categories

DP Design Steps

1. Identify the problem as DP – check optimal substructure and overlapping subproblems
2. Define the state – what does dp[i][j] represent?
3. Formulate the recurrence – how does dp[i][j] relate to previous states?
4. Define base cases – smallest subproblems (dp[0], dp[0][0], etc.)
5. Choose approach – top‑down (memoization) or bottom‑up (tabulation)
6. Implement – write the code
7. Optimise – reduce space (2 rows → 1 row → O(1))

Classic DP Problems

1. Fibonacci Numbers

// Top‑down (Memoization)
int fib(int n, int[] memo) {
    if (n <= 1) return n;
    if (memo[n] != 0) return memo[n];
    return memo[n] = fib(n - 1, memo) + fib(n - 2, memo);
}

// Bottom‑up (Tabulation)
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 Optimised
int fib(int n) {
    if (n <= 1) return n;
    int a = 0, b = 1;
    for (int i = 2; i <= n; i++) {
        int c = a + b;
        a = b;
        b = c;
    }
    return b;
}

2. 0/1 Knapsack

// Bottom‑up Tabulation
int knapsack(int[] wt, int[] val, int W) {
    int n = wt.length;
    int[][] dp = new int[n + 1][W + 1];
    for (int i = 1; i <= n; i++) {
        for (int w = 1; w <= W; w++) {
            if (wt[i - 1] <= w) {
                dp[i][w] = Math.max(dp[i - 1][w], val[i - 1] + dp[i - 1][w - wt[i - 1]]);
            } else {
                dp[i][w] = dp[i - 1][w];
            }
        }
    }
    return dp[n][W];
}

// Space Optimised (1D array)
int knapsack(int[] wt, int[] val, int W) {
    int n = wt.length;
    int[] dp = new int[W + 1];
    for (int i = 0; i < n; i++) {
        for (int w = W; w >= wt[i]; w--) {
            dp[w] = Math.max(dp[w], val[i] + dp[w - wt[i]]);
        }
    }
    return dp[W];
}

3. Longest Common Subsequence (LCS)

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] = 1 + dp[i - 1][j - 1];
            } else {
                dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
            }
        }
    }
    return dp[m][n];
}

4. Edit Distance (Levenshtein)

int editDistance(String s1, String s2) {
    int m = s1.length(), n = s2.length();
    int[][] dp = new int[m + 1][n + 1];
    for (int i = 0; i <= m; i++) dp[i][0] = i;
    for (int j = 0; j <= n; j++) dp[0][j] = j;
    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];
            } else {
                dp[i][j] = 1 + Math.min(Math.min(dp[i - 1][j], dp[i][j - 1]), dp[i - 1][j - 1]);
            }
        }
    }
    return dp[m][n];
}

5. Longest Increasing Subsequence (LIS)

int LIS(int[] nums) {
    int n = nums.length;
    int[] dp = new int[n];
    Arrays.fill(dp, 1);
    int max = 1;
    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);
            }
        }
        max = Math.max(max, dp[i]);
    }
    return max;
}

6. Unique Paths (Grid)

int uniquePaths(int m, int n) {
    int[][] dp = new int[m][n];
    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];
}

7. House Robber

int rob(int[] nums) {
    int n = nums.length;
    if (n == 0) return 0;
    if (n == 1) return nums[0];
    int[] dp = new int[n];
    dp[0] = nums[0];
    dp[1] = Math.max(nums[0], nums[1]);
    for (int i = 2; i < n; i++) {
        dp[i] = Math.max(dp[i - 1], dp[i - 2] + nums[i]);
    }
    return dp[n - 1];
}

// Space Optimised
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;
}

8. Coin Change (Ways)

int coinChangeWays(int[] coins, int amount) {
    int[] dp = new int[amount + 1];
    dp[0] = 1;
    for (int coin : coins) {
        for (int i = coin; i <= amount; i++) {
            dp[i] += dp[i - coin];
        }
    }
    return dp[amount];
}

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

9. Matrix Chain Multiplication

int matrixChain(int[] dims) {
    int n = dims.length - 1;
    int[][] dp = new int[n][n];
    for (int len = 2; len <= n; len++) {
        for (int i = 0; i <= n - len; i++) {
            int j = i + len - 1;
            dp[i][j] = Integer.MAX_VALUE;
            for (int k = i; k < j; k++) {
                int cost = dp[i][k] + dp[k + 1][j] + dims[i] * dims[k + 1] * dims[j + 1];
                dp[i][j] = Math.min(dp[i][j], cost);
            }
        }
    }
    return dp[0][n - 1];
}

DP Optimisation Techniques

Common DP Patterns Reference

Pattern	DP[i] or DP[i][j] meaning	Recurrence
Fibonacci	dp[n] = nth fibonacci number	dp[i] = dp[i-1] + dp[i-2]
0/1 Knapsack	dp[i][w] = max value with first i items, capacity w	dp[i][w] = max(dp[i-1][w], val[i] + dp[i-1][w-wt[i]])
LCS	dp[i][j] = LCS length of s1[0..i], s2[0..j]	match: dp[i-1][j-1]+1; else max(dp[i-1][j], dp[i][j-1])
Edit Distance	dp[i][j] = edit distance between s1[0..i], s2[0..j]	match: dp[i-1][j-1]; else 1 + min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1])
LIS	dp[i] = LIS length ending at index i	dp[i] = max(dp[j] + 1) for j < i, nums[j] < nums[i]
Unique Paths	dp[i][j] = ways to reach (i,j)	dp[i][j] = dp[i-1][j] + dp[i][j-1]
House Robber	dp[i] = max rob amount up to house i	dp[i] = max(dp[i-1], dp[i-2] + nums[i])
Coin Change	dp[i] = min coins for amount i	dp[i] = min(1 + dp[i-coin]) for coin in coins

Complexity Summary

Problem	Time	Space
Fibonacci	O(n)	O(1)
0/1 Knapsack	O(nW)	O(W)
LCS	O(mn)	O(mn) → O(n) optimised
Edit Distance	O(mn)	O(mn) → O(n) optimised
LIS	O(n²) → O(n log n) with binary search	O(n)
Unique Paths	O(mn)	O(n) optimised
House Robber	O(n)	O(1)
Coin Change (min)	O(amount * coins)	O(amount)
Matrix Chain	O(n³)	O(n²)

DP Tips

• Start with recursion – write naive recursive solution first
• Add memoization – cache results of recursive calls
• Convert to tabulation – if recursion stack is a concern
• Identify the state – what parameters define the subproblem?
• Identify the recurrence – how does the state relate to smaller states?
• Identify the base case – what are the smallest subproblems?
• Identify the answer – what state gives the final answer?
• Optimise space – only keep previous row/col when possible
• Consider binary search – for LIS and similar problems
• Look for patterns – many problems share the same DP structure