What is dynamic programming?
Dynamic programming is a technique that allows us to solve a class of problems with overlapping subproblems and optimal substructure.
Dynamic programming is also a technique that trades space for time. With dynamic programming, a problem with exponential number of subproblems can often be solved in polynomial time.
The time complexity of dynamic programming problems is usually O(MN), where M = number of subproblems, N = time complexity of subproblems.
Characteristics of dynamic programming
Overlapping subproblem: the original problem has multiple instances of the same subproblem.
Optimal substructure: the solution to the original problem can be constructed from solutions of subproblems.
Dynamic programming implementations
The two dynamic programming implementations are:
- top down (DFS + memoization)
- bottom up (tabulation
To solve dynamic programming problems, you need:
- the problem defined as relatable subproblems
- recurrence relation to relate the sub-solutions to the original solution
- base cases for the recurrence relation
Common dynamic programming questions
Here are 6 common dynamic programming questions:
- Knapsack
- Longest increasing subsequence
- Longest common subsequence (edit distance)
- Matrix chain multiplication
- Kadane's algorithm
- Distinct Ways
Top comments (0)