Define the Structure:
- Break down the problem into smaller subproblems and define the relationship between the overall problem and its subproblems.
Formulate a Recursive Solution:
- Develop a recursive solution to the problem, expressing the solution in terms of solutions to smaller subproblems.
Memoization or Tabulation:
- Implement a mechanism to store and retrieve solutions to subproblems to avoid redundant computations.
- This can be done using memoization (top-down approach) or tabulation (bottom-up approach).
Construct the Optimal Solution:
- Use the stored solutions to subproblems to construct the optimal solution to the overall problem.
Dynamic programming (DP) encompasses several types or approaches, each with its own characteristics and use cases. Here are some common types of dynamic programming:
1. Top-Down (Memoization):
- Also known as recursive with memoization.
- The problem is solved in a recursive manner, and the solutions to subproblems are stored (memoized) to avoid redundant calculations.
- Typically implemented using recursion and a data structure (e.g., a dictionary) to store intermediate results.
Example:
pythonCopy code
def fib(n, memo={}):
if n <= 1:
return n
elif n not in memo:
memo[n] = fib(n-1, memo) + fib(n-2, memo)
return memo[n]
2. Bottom-Up (Tabulation):
- Also known as iterative DP.
- The problem is solved by solving subproblems in a bottom-up manner, starting from the smallest subproblems.
- The solutions to subproblems are stored in a table, and the table is filled iteratively to solve the overall problem.
Example:
pythonCopy code
def fib(n):
if n <= 1:
return n
table = [0] * (n + 1)
table[1] = 1
for i in range(2, n + 1):
table[i] = table[i-1] + table[i-2]
return table[n]
3. State Transition Matrix:
- Used when the state transition of the problem can be expressed in the form of a matrix.
- The matrix represents the transitions between states, and matrix exponentiation can be applied to find the solution efficiently.
Example: Solving linear recurrence relations using matrix exponentiation.
4. Optimal Substructure:
- In problems with optimal substructure, the optimal solution to the overall problem can be constructed from optimal solutions to its subproblems.
- Typically involves breaking down the problem into subproblems and expressing the overall solution in terms of the solutions to subproblems.
Example: The shortest path problem, where the optimal path from A to C is composed of optimal paths from A to B and B to C.
5. State Compression:
- Used when the state space is large, and storing all possible states is impractical.
- Instead of storing all states, compressed representations of states are used, leading to more efficient memory usage.
Example: The subset sum problem, where the state space can be compressed using bitmasking.
6. Bitmask DP:
- Applied when the state space can be efficiently represented using binary masks.
- Often used in combinatorial optimization problems where subsets of elements are considered.
Example: Traveling Salesman Problem with bitmask DP to represent subsets of cities visited.
7. Knapsack DP:
- Applied to problems that involve optimization with constraints, where items must be selected to maximize or minimize a value while respecting constraints.
Example: 0/1 Knapsack Problem, where items have weights and values, and the goal is to maximize the total value within a weight constraint.
2. Fibonacci Series
The Fibonacci Series is a sequence of integers where the next integer in the series is the sum of the previous two.
It’s defined by the following recursive formula:
.There are many ways to calculate the
term of the Fibonacci series, and below we’ll look at three common approaches.
2.1. The Recursive Approach
To compute
in the recursive approach, we first try to find the solutions to
and
. But to find
, we need to find
and
. This continues until we reach the base cases:
and
.In the image below, we can see a tree of subproblems we need to solve in order to get
:
One drawback to this approach is that it requires computing the same Fibonacci numbers multiple times in order to get our solution.
Let’s see if we can get rid of this redundant work.
2.2. The Top-Down Approach
The first dynamic programming approach we’ll use is the top-down approach. The idea here is similar to the recursive approach, but the difference is that we’ll save the solutions to subproblems we encounter.
This way, if we run into the same subproblem more than once, we can use our saved solution instead of having to recalculate it. This allows us to compute each subproblem exactly one time.
This dynamic programming technique is called memoization. We can see how our tree of subproblems shrinks when we use memoization:
2.3. The Bottom-Up Approach
In the bottom-up dynamic programming approach, we’ll reorganize the order in which we solve the subproblems.
We’ll compute
, then
, then
, and so on:
This will allow us to compute the solution to each problem only once, and we’ll only need to save two intermediate results at a time.
For example, when we’re trying to find
, we only need to have the solutions to
and
available. Similarly, for
, we only need to have the solutions to
and
.
This will allow us to use less memory space in our code.