Dynamic Programming Algorithms Cheat Sheet

Dynamic programming (DP) is a powerful technique for solving optimization problems by breaking them down into simpler subproblems. This cheat sheet covers 10 essential dynamic programming algorithms, their steps, examples, and time complexities.

Core Concepts of Dynamic Programming

Memoization

Memoization is a technique used in dynamic programming to store the results of expensive function calls and reuse them when the same inputs occur again. This prevents redundant calculations and speeds up the algorithm.

Tabulation

Tabulation, also known as the bottom-up approach, involves filling up a table (usually an array or matrix) iteratively, starting with the simplest subproblems, until the final solution is reached. This approach is often preferred when it’s easier to build the solution from the base cases.

Overlapping Subproblems

Dynamic programming problems often have overlapping subproblems, meaning the same subproblems are solved multiple times. By storing the results of these subproblems (either through memoization or tabulation), the overall computation can be significantly reduced.

Optimal Substructure

A problem exhibits optimal substructure if an optimal solution to the problem contains optimal solutions to its subproblems. This property is essential for dynamic programming, as it allows the problem to be broken down into smaller, manageable components that can be solved independently.

1. 0/1 Knapsack Problem

Description: Given a set of items, each with a weight and a value, determine the maximum value that can be obtained by selecting items without exceeding a given weight capacity.

Steps:

  1. Create a DP table where rows represent items and columns represent weights up to the capacity.
  2. Initialize the first row and first column to 0 (no items or 0 capacity).
  3. For each item, check if including it provides a better value than excluding it, and update the table accordingly.
  4. The value in the bottom-right corner of the table is the maximum value obtainable.

Time Complexity: O(n * W) where n is the number of items and W is the capacity.

0/1 Knapsack Example:

Items: [{weight: 1, value: 1}, {weight: 3, value: 4}, {weight: 4, value: 5}, {weight: 5, value: 7}]
Capacity: 7

DP Table:
   0 1 2 3 4 5 6 7
0  0 0 0 0 0 0 0 0
1  0 1 1 1 1 1 1 1
2  0 1 1 4 5 5 5 5
3  0 1 1 4 5 6 6 9
4  0 1 1 4 5 7 8 9

Max Value: 9

2. Longest Common Subsequence (LCS)

Description: Given two sequences, find the length of the longest subsequence that appears in both sequences.

Steps:

  1. Create a DP table where rows represent characters of the first sequence and columns represent characters of the second sequence.
  2. Initialize the first row and first column to 0 (base case).
  3. For each character pair, if they match, add 1 to the diagonal value; otherwise, take the maximum value from the left or top cell.
  4. The value in the bottom-right corner is the length of the LCS.

Time Complexity: O(m * n) where m and n are the lengths of the two sequences.

LCS Example:

Sequences: "ABCBDAB", "BDCAB"

DP Table:
   0 0 0 0 0 0
0  0 0 1 1 1 1
0  0 1 1 1 2 2
0  0 1 1 2 2 3
0  0 1 1 2 3 3

LCS Length: 4 ("BCAB")

3. Longest Increasing Subsequence (LIS)

Description: Given an unsorted array of integers, find the length of the longest increasing subsequence.

Steps:

  1. Create an array to store the length of the LIS up to each index, initialized to 1.
  2. For each element, compare it with all previous elements to find if it can extend any previous LIS.
  3. Update the length of the LIS for each element based on the maximum length found.
  4. The maximum value in the array is the length of the LIS.

Time Complexity: O(n^2)

LIS Example:

Array: [10, 22, 9, 33, 21, 50, 41, 60, 80]

LIS Length: 6 (10, 22, 33, 50, 60, 80)

4. Coin Change Problem

Description: Given an amount and a list of coin denominations, find the number of ways to make the amount using the coins.

Steps:

  1. Create a DP array where each index represents the number of ways to make that amount, initialized to 0.
  2. Set dp[0] to 1 (base case: one way to make amount 0).
  3. For each coin, update the DP array by adding the number of ways to make each amount using the coin.
  4. The value at dp[amount] is the number of ways to make the amount.

Time Complexity: O(n * m) where n is the amount and m is the number of coin denominations.

Coin Change Example:

Coins: [1, 2, 5]
Amount: 5

DP Array: [1, 1, 2, 2, 3, 4]

Number of Ways: 4 (1+1+1+1+1, 1+1+1+2, 1+2+2, 5)

5. Matrix Chain Multiplication

Description: Given a sequence of matrices, find the most efficient way to multiply them together. The problem is to find the minimum number of multiplications needed to multiply the sequence.

Steps:

  1. Create a DP table to store the minimum number of multiplications needed to multiply matrices from index i to j.
  2. Initialize the diagonal to 0 (multiplying one matrix requires no multiplication).
  3. For each subproblem, calculate the cost of multiplying matrices by splitting the problem at different points and taking the minimum cost.
  4. The value in the top-right corner of the DP table is the minimum number of multiplications needed.

Time Complexity: O(n^3)

Matrix Chain Multiplication Example:

Matrices: A1 (10x20), A2 (20x30), A3 (30x40)

Minimum Number of Multiplications: 18000

6. Edit Distance

Description: Given two strings, find the minimum number of operations required to convert one string into the other. Operations include insert, delete, and replace.

Steps:

  1. Create a DP table where rows represent characters of the first string and columns represent characters of the second string.
  2. Initialize the first row and first column to represent the cost of converting an empty string to the respective prefixes.
  3. For each character pair, if they match, copy the diagonal value; otherwise, take the minimum value from the left, top, or diagonal cell and add 1.
  4. The value in the bottom-right corner is the edit distance.

Time Complexity: O(m * n) where m and n are the lengths of the two strings.

Edit Distance Example:

Strings: "sunday", "saturday"

Edit Distance: 3 (insert 'a', insert 't', replace 'y' with 'd')

7. Subset Sum Problem

Description: Given a set of positive integers and a value sum, determine if there is a subset of the given set with a sum equal to the given sum.

Steps:

  1. Create a DP table where rows represent elements and columns represent possible sums up to the given sum.
  2. Initialize the first column to true (sum of 0 is always possible) and the first row to false (except for sum 0).
  3. For each element, update the DP table by including or excluding the current element.
  4. The value at the bottom-right corner of the table indicates whether the subset with the given sum exists.

Time Complexity: O(n * sum)

Subset Sum Example:

Set: [3, 34, 4, 12, 5, 2]
Sum: 9

Result: True (subset {4, 5})

8. Rod Cutting Problem

Description: Given a rod of length n and a list of prices for different lengths, determine the maximum revenue obtainable by cutting the rod into pieces.

Steps:

  1. Create a DP array to store the maximum revenue obtainable for each length.
  2. Initialize the array with 0 for length 0.
  3. For each length, determine the maximum revenue by considering all possible cuts and updating the DP array.
  4. The value at the last index of the DP array is the maximum revenue obtainable.

Time Complexity: O(n^2)

Rod Cutting Example:

Length: 8
Prices: [1, 5, 8, 9, 10, 17, 17, 20]

Maximum Revenue: 22 (cut into lengths 2 and 6)

9. Egg Dropping Problem

Description: Given n eggs and a building with k floors, find the minimum number of attempts needed to find the highest floor from which an egg can be dropped without breaking.

Steps:

  1. Create a DP table where rows represent the number of eggs and columns represent the number of floors.
  2. Initialize the first row to 0 (no eggs) and the first column to represent the number of attempts needed for one floor.
  3. For each egg-floor combination, update the DP table by considering all possible drops and taking the minimum of the maximum attempts needed.
  4. The value in the bottom-right corner is the minimum number of attempts needed.

Time Complexity: O(n * k^2)

Egg Dropping Example:

Eggs: 2
Floors: 10

Minimum Attempts: 4

10. Palindrome Partitioning

Description: Given a string, find the minimum number of cuts needed to partition it into substrings, each of which is a palindrome.

Steps:

  1. Create a DP table to store the minimum cuts needed for each substring.
  2. Initialize the table with high values, and set dp[i][i] to 0 (a single character is always a palindrome).
  3. For each substring, check if it is a palindrome and update the DP table with the minimum cuts needed.
  4. The value in the bottom-right corner is the minimum number of cuts needed.

Time Complexity: O(n^2)

Palindrome Partitioning Example:

String: "ababbbabbababa"

Minimum Cuts: 3 ("aba | bbb | abba | ba")

Conclusion

Dynamic programming is a versatile technique for solving complex problems by breaking them down into simpler subproblems. This cheat sheet provides a comprehensive overview of 10 key dynamic programming algorithms, helping you master this powerful tool in your algorithmic toolbox.