Dynamic Programming
Dynamic Programming (DP) is an algorithmic technique used to solve complex problems by
breaking them down into smaller subproblems
solving each subproblem only once
storing the solutions to subproblems to avoid redundant computation.
Key Characteristics
Divide and Conquer: Break down the problem into smaller subproblems.
Overlapping Subproblems: Subproblems may have some overlap, meaning that some subproblems may be identical or have similar solutions.
Optimal Substructure: The problem can be solved optimally by solving its subproblems optimally.
Memoization: Store the solutions to subproblems to avoid redundant computation.
How Dynamic Programming Works
Identify the problem: Determine if the problem can be solved using DP.
Define the state: Identify the variables that describe the state of the problem.
Define the transition: Determine how to transition from one state to another.
Initialize the DP table: Create a table to store the solutions to subproblems.
Fill the DP table: Iterate over the states, solving each subproblem and storing its solution.
Extract the solution: The solution to the original problem is stored in the DP table.
Types of Dynamic Programming
Top-Down DP: Start with the original problem and recursively break it down into smaller subproblems.
Bottom-Up DP: Start with the smallest subproblems and iteratively build up to the original problem.
Advantages
Efficient: Avoids redundant computation by storing solutions to subproblems.
Scalable: Can solve large problems by breaking them down into manageable subproblems.
Optimal: Guarantees optimal solutions by solving subproblems optimally.
Common Applications
Longest Common Subsequence
Example: Fibonacci Series
Problem: Find the nth Fibonacci number.
Top-Down DP Solution
Using recursion:
def fibonacci(n, memo = {}):
if n in memo: return memo[n]
if n <= 2: return 1
memo[n] = fibonacci(n-1, memo) + fibonacci(n-2, memo)
return memo[n]
Bottom-Up DP Solution
Using loop iteration:
def fibonacci(n):
dp = [0] * (n+1)
dp[1] = dp[2] = 1
for i in range(3, n+1):
dp[i] = dp[i-1] + dp[i-2]
return dp[n]