DP - s50600822/Notes GitHub Wiki
A list of classic problems in dynamic programming from easier to harder:
| Problem | Description | Time Complexity | Space Complexity |
|---|---|---|---|
| Fibonacci Sequence | Calculate the nth number in the Fibonacci sequence | O(n) | O(1) |
| Climbing Stairs | Count the number of ways to climb n stairs if you can take 1 or 2 steps at a time | O(n) | O(1) |
| Coin Change | Determine the minimum number of coins needed to make a given amount of change | O(n * amount) | O(amount) |
| Maximum Subarray | Find the contiguous subarray within an array that has the largest sum | O(n) | O(1) |
| Longest Increasing Subsequence | Find the length of the longest increasing subsequence in an array | O(n^2) | O(n) |
| Edit Distance | Calculate the minimum number of operations to transform one string into another | O(m * n) | O(min(m, n)) |
| 0/1 Knapsack | Determine the maximum value that can be obtained from a knapsack of capacity W, given a set of items with values and weights | O(n * W) | O(W) |
| Matrix Chain Multiplication | Determine the optimal order in which to multiply a set of matrices | O(n^3) | O(n^2) |
| Longest Common Subsequence | Find the length of the longest subsequence that is common to two strings | O(m * n) | O(min(m, n)) |
| Unique Paths | Count the number of unique paths from the top-left corner to the bottom-right corner of a grid | O(m * n) | O(min(m, n)) |
| Longest Palindromic Substring | Find the longest substring of a given string that is also a palindrome | O(n^2) | O(n^2) |
| Regular Expression Matching | Determine if a given string matches a given regular expression | O(m * n) | O(n) |
| Partition Equal Subset Sum | Determine if a given set can be partitioned into two subsets with equal sum | O(n * sum) | O(sum) |
| Maximum Product Subarray | Find the contiguous subarray within an array that has the largest product | O(n) | O(1) |
| Minimum Path Sum | Find the minimum sum of a path from the top-left corner to the bottom-right corner of a grid | O(m * n) | O(1) |
| Decode Ways | Determine the number of ways to decode a given string | O(n) | O(1) |
| Egg Drop | Determine the minimum number of attempts needed to find the floor from which an egg will break, given a certain number of eggs and floors | O(n^2) | O(n) |
| Word Break | Determine if a given string can be segmented into a space-separated sequence of dictionary words | O(n^2) | O(n) |
| Palindrome Partitioning | Determine the minimum number of cuts needed to partition a given string into palindromes | O(n^2) | O(n^2) |
| Maximum Sum Increasing Subsequence | Find the sum of the increasing subsequence with the largest sum in an array | O(n^2) | O(n) |