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