Dynamic Programming Fundamentals

Generated on 2025-07-10 02:00:08 Algorithm Cheatsheet for Technical Interviews

---

Dynamic Programming Fundamentals Cheatsheet

1. Quick Overview

• What is it? A problem-solving technique that breaks down a complex problem into overlapping subproblems, solves each subproblem only once, and stores their solutions to avoid redundant computations. Think of it as “memoization with tabulation.”
• When to use it?
  • Optimal substructure: The optimal solution to the problem contains the optimal solutions to its subproblems.
  • Overlapping subproblems: The problem can be broken down into subproblems which are reused multiple times. Examples: Fibonacci sequence, finding shortest paths, sequence alignment.
  • Optimization problems (minimize, maximize, count).
  • When a recursive solution is too slow (due to redundant calculations).

2. Time & Space Complexity

Approach	Time Complexity	Space Complexity
Memoization	O(number of subproblems)	O(number of subproblems + recursion depth)
Tabulation	O(number of subproblems)	O(size of the DP table)

• Note: Tabulation often has better constant factors than memoization due to the overhead of recursive calls. Space complexity of memoization can be reduced if only the previous row is needed in tabulation.

3. Implementation

General Approach:

1. Define the subproblem: Clearly define what each state in your DP table represents.
2. Identify the base cases: Determine the simplest subproblems that can be solved directly.
3. Write the recurrence relation: Express the solution to a subproblem in terms of the solutions to smaller subproblems.
4. Memoization (Top-Down):
   • Create a lookup table (e.g., a dictionary or array) to store the results of subproblems.
   • Implement a recursive function that:
     • Checks if the result for the current subproblem is already in the lookup table. If so, return it.
     • Otherwise, compute the result using the recurrence relation, store it in the lookup table, and return it.
5. Tabulation (Bottom-Up):
   • Create a DP table (e.g., a 2D array) to store the results of subproblems.
   • Initialize the base cases in the DP table.
   • Iterate through the DP table in a specific order (usually from smaller subproblems to larger ones), filling in the table entries using the recurrence relation.

Python Example (Fibonacci - Tabulation):

def fibonacci_tabulation(n):
    """
    Calculates the nth Fibonacci number using tabulation (bottom-up).
    Time: O(n), Space: O(n)
    """
    dp = [0] * (n + 1)  # DP table to store Fibonacci numbers
    dp[0] = 0
    if n > 0:
        dp[1] = 1  # Base cases
    for i in range(2, n + 1):
        dp[i] = dp[i - 1] + dp[i - 2]  # Recurrence relation
    return dp[n]

# Example usage
n = 10
result = fibonacci_tabulation(n)
print(f"Fibonacci({n}) = {result}")

Java Example (Fibonacci - Memoization):

import java.util.Arrays;

class Solution {
    public int fibonacciMemoization(int n) {
        int[] memo = new int[n + 1];
        Arrays.fill(memo, -1); // Initialize memo table with -1 (indicating not calculated)
        return fibonacciMemoizationHelper(n, memo);
    }

    private int fibonacciMemoizationHelper(int n, int[] memo) {
        if (n <= 1) {
            return n; // Base cases
        }
        if (memo[n] != -1) {
            return memo[n]; // Return cached result
        }
        memo[n] = fibonacciMemoizationHelper(n - 1, memo) + fibonacciMemoizationHelper(n - 2, memo); // Recurrence
        return memo[n];
    }

    public static void main(String[] args) {
        Solution sol = new Solution();
        int n = 10;
        int result = sol.fibonacciMemoization(n);
        System.out.println("Fibonacci(" + n + ") = " + result);
    }
}

C++ Example (Fibonacci - Tabulation):

#include <iostream>
#include <vector>

using namespace std;

int fibonacciTabulation(int n) {
    /*
    Calculates the nth Fibonacci number using tabulation (bottom-up).
    Time: O(n), Space: O(n)
    */
    vector<int> dp(n + 1, 0); // DP table to store Fibonacci numbers
    dp[0] = 0;
    if (n > 0) {
        dp[1] = 1; // Base cases
    }
    for (int i = 2; i <= n; ++i) {
        dp[i] = dp[i - 1] + dp[i - 2]; // Recurrence relation
    }
    return dp[n];
}

int main() {
    int n = 10;
    int result = fibonacciTabulation(n);
    cout << "Fibonacci(" << n << ") = " << result << endl;
    return 0;
}

4. Common Patterns

• 1D DP: Uses a single-dimensional array to store subproblem solutions. Examples: Fibonacci, Climbing Stairs, House Robber.
• 2D DP: Uses a two-dimensional array to store subproblem solutions. Examples: Longest Common Subsequence (LCS), Edit Distance, Knapsack Problem.
• Subsequence/Substring Problems: Finding the longest increasing subsequence, longest palindromic substring, etc.
• Knapsack Problem: Choosing items to maximize value within a weight constraint.
• Coin Change Problem: Finding the minimum number of coins to make a given amount.
• Matrix Chain Multiplication: Optimizing the order of matrix multiplications.
• Traveling Salesman Problem (TSP): Finding the shortest possible route that visits each city exactly once and returns to the origin city (often uses bitmasking).

5. Pro Tips

• State Definition is Key: The most important part is defining what your dp[i] or dp[i][j] represents. Spend time thinking about this.
• Initialization: Pay close attention to initializing the DP table, especially the base cases. Incorrect initialization can lead to incorrect results.
• Iteration Order: The order in which you fill the DP table in the tabulation approach is crucial. Make sure you are calculating the subproblems in the correct order.
• Space Optimization: In some cases, you can reduce the space complexity of tabulation by only storing the previous row or column of the DP table (if you don’t need the entire table).
• Memoization vs. Tabulation:
  • Memoization can be easier to implement if the recurrence relation is complex.
  • Tabulation can be more efficient in some cases due to the elimination of recursive call overhead.
• Debugging: Print the DP table during execution to verify that it’s being filled correctly.
• Don’t be afraid to start with recursion: If you’re having trouble with DP, start by writing a recursive solution first. Then, identify the overlapping subproblems and memoize the results.

6. Practice Problems

1. LeetCode 70. Climbing Stairs: You are climbing a staircase. It takes n steps to reach the top. Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top?
2. LeetCode 1143. Longest Common Subsequence: Given two strings text1 and text2, return the length of their longest common subsequence. If there is no common subsequence, return 0.
3. LeetCode 322. Coin Change: You are given coins of different denominations and a total amount of money amount. Write a function to compute the fewest number of coins that you need to make up that amount. If that amount of money cannot be made up by any combination of the coins, return -1.

7. Templates

Python:

# 1D DP - Template
def solve_1d_dp(n):
    dp = [0] * (n + 1)
    # Initialize base cases: dp[0] = ...
    # Iterate and fill the dp table
    for i in range(1, n + 1):
        # dp[i] = ... (recurrence relation)
        pass
    return dp[n]

# 2D DP - Template
def solve_2d_dp(m, n):
    dp = [[0] * (n + 1) for _ in range(m + 1)]
    # Initialize base cases: dp[0][j] = ..., dp[i][0] = ...
    # Iterate and fill the dp table
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            # dp[i][j] = ... (recurrence relation)
            pass
    return dp[m][n]

Java:

// 1D DP - Template
class Solution {
    public int solve1DDp(int n) {
        int[] dp = new int[n + 1];
        // Initialize base cases: dp[0] = ...
        // Iterate and fill the dp table
        for (int i = 1; i <= n; i++) {
            // dp[i] = ... (recurrence relation)
        }
        return dp[n];
    }

    // 2D DP - Template
    public int solve2DDp(int m, int n) {
        int[][] dp = new int[m + 1][n + 1];
        // Initialize base cases: dp[0][j] = ..., dp[i][0] = ...
        // Iterate and fill the dp table
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                // dp[i][j] = ... (recurrence relation)
            }
        }
        return dp[m][n];
    }
}

C++:

#include <iostream>
#include <vector>

using namespace std;

// 1D DP - Template
int solve1DDp(int n) {
    vector<int> dp(n + 1, 0);
    // Initialize base cases: dp[0] = ...
    // Iterate and fill the dp table
    for (int i = 1; i <= n; ++i) {
        // dp[i] = ... (recurrence relation)
    }
    return dp[n];
}

// 2D DP - Template
int solve2DDp(int m, int n) {
    vector<vector<int>> dp(m + 1, vector<int>(n + 1, 0));
    // Initialize base cases: dp[0][j] = ..., dp[i][0] = ...
    // Iterate and fill the dp table
    for (int i = 1; i <= m; ++i) {
        for (int j = 1; j <= n; ++j) {
            // dp[i][j] = ... (recurrence relation)
        }
    }
    return dp[m][n];
}