This is GPT generated
Dynamic Programming (DP) is a method for solving complex problems by breaking them down into simpler subproblems. It is particularly useful when the problem can be divided into overlapping subproblems, and there is an optimal substructure, meaning the optimal solution to the entire problem depends on the optimal solutions to its subproblems.
The key idea behind dynamic programming is to store the solutions to subproblems so that they can be reused later, avoiding the need to recompute them. This technique is a powerful tool for optimization problems where brute-force solutions would be inefficient.
Two Main Techniques in Dynamic Programming:
Memoization (Top-Down Approach)
In this approach, the problem is solved recursively by breaking it down into subproblems. The results of the subproblems are stored in a cache (usually a dictionary or array), so that if a subproblem is encountered again, the stored solution can be used instead of recalculating it.
Memoization essentially turns a recursive solution into an efficient one by eliminating redundant calculations.
Example: Recursive Fibonacci with Memoization:
def fibonacci(n, memo={}):
if n in memo:
return memo[n]
if n <= 1:
return n
memo[n] = fibonacci(n-1, memo) + fibonacci(n-2, memo)
return memo[n]
print(fibonacci(10)) _# Output: 55_Tabulation (Bottom-Up Approach)
In the tabulation approach, the problem is solved by solving all smaller subproblems first and then building up to solve the original problem. This is done iteratively and usually involves filling up a table (often an array) with the solutions to subproblems.
The tabulation method avoids recursion altogether and is often faster for certain problems because it eliminates the overhead of recursive calls.
Example: Fibonacci with Tabulation:
def fibonacci(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]
print(fibonacci(10)) _# Output: 55_Example: Longest Common Subsequence (LCS): Given two strings, find the length of their longest common subsequence.
def lcs(X, Y):
m = len(X)
n = len(Y)
dp = [[0] * (n+1) for _ in range(m+1)]
for i in range(1, m+1):
for j in range(1, n+1):
if X[i-1] == Y[j-1]:
dp[i][j] = dp[i-1][j-1] + 1
else:
dp[i][j] = max(dp[i-1][j], dp[i][j-1])
return dp[m][n]
print(lcs("AGGTAB", "GXTXAYB")) _# Output: 4_tags: algorithms