Dynamic programming (DP) is an algorithmic technique used to solve complex problems in computer science by breaking them down into simpler subproblems of the same nature. It’s particularly useful for solving optimization problems where solutions to subproblems can be reused to avoid redundant computations, thereby improving efficiency.
Key features of dynamic programming:
Optimal Substructure: A problem has an optimal substructure if an optimal solution can be constructed efficiently from optimal solutions of its subproblems.
Overlapping Subproblems: Subproblems recur many times and solutions to these subproblems can be cached and reused rather than recomputed.
Steps that are typically used for solving a Dynamic programming problem:
Define the Problem: Identify the problem that can be divided into smaller subproblems within it that have the same nature.
Construct a Recurrence Relation: Express the solution of the problem in terms of solutions to its smaller subproblems.
Memoization or Tabulation: Implement the recurrence relation either using
These are for storing the intermediate results and avoiding redundant computations.
Example of Dynamic Programming Problems
| Problems | Time Complexity |
|---|---|
| Longest Common Subsequence (LCS) | O ( M * N ). M and N are the lengths of the first and second sequence respectively. |
| Longest Increasing Subsequence (LIS) | O ( N 2 ). N is the number of elements in the sequence. |
| Matrix Chain Multiplication | O ( N 3 ). N is the number of matrices. |
| Longest Palindromic Substring | O ( N 2 ). N is the length of the string. |
| Maximum Sum Subarray | O ( N ). N is the number of elements in the subarray. |
| 0-1 Knapsack | O ( N * M ). N is the capacity of the knapsack and M is the number of weights available for putting into the knapsack. |
| Coins Change Problem | O ( N * M ). N is the bigger coin to be exchanged and M is the number of smaller coins to be used for exchanging |
| Integer Partitioning Problem | O ( N * M ). N is the bigger number to be partitioned and M is the number of smaller integers to be used for partitioning. |
| Maximum Sum SubRectangle using aggregate rectangles | O ( N 4 ). N is the number of elements in the rows / columns in the rectangle. |
| Maximum Sum SubRectangle using Kadane’s algorithm | O ( N 3 ). N is the number of elements in the rows / columns in the rectangle. |