Python dynamic programming examples

Python dynamic programming examples

Here are some examples of using dynamic programming (DP) in Python:

1. Fibonacci Series:

The Fibonacci series is a classic example of DP. The problem is to find the nth Fibonacci number, where each number is the sum of the previous two.

def fibonacci(n):
if n <= 1:
return n
dp = [0] * (n + 1)
dp[0], dp[1] = 0, 1
for i in range(2, n + 1):
dp[i] = dp[i-1] + dp[i-2]
return dp[n]
print(fibonacci(10))  # Output: 55

2. Longest Increasing Subsequence (LIS):

Find the length of the longest increasing subsequence in an array.

def lis(arr):
n = len(arr)
dp = [1] * n
for i in range(1, n):
for j in range(i):
if arr[i] > arr[j]:
dp[i] = max(dp[i], dp[j] + 1)
return max(dp)
arr = [10, 22, 9, 33, 21]
print(lis(arr))  # Output: 4

3. Minimum Edit Distance (MED):

Find the minimum edit distance between two strings.

def med(s1, s2):
m, n = len(s1), len(s2)
dp = [[0] * (n + 1) for _ in range(m + 1)]
for i in range(m + 1):
for j in range(n + 1):
if i == 0:
dp[i][j] = j
elif j == 0:
dp[i][j] = i
elif s1[i-1] == s2[j-1]:
dp[i][j] = dp[i-1][j-1]
else:
dp[i][j] = 1 + min(dp[i-1][j], dp[i][j-1])
return dp[m][n]
s1 = "kitten"
s2 = "sitting"
print(med(s1, s2))  # Output: 3

4. Knapsack Problem:

Find the maximum value that can be put in a knapsack of capacity W using items with weights and values given.

def knapsack(weights, values, W):
n = len(weights)
dp = [[0] * (W + 1) for _ in range(n + 1)]
for i in range(n + 1):
for j in range(W + 1):
if i == 0 or j == 0:
dp[i][j] = 0
elif weights[i-1] <= j:
dp[i][j] = max(values[i-1] + dp[i-1][j-weights[i-1]], dp[i-1][j])
else:
dp[i][j] = dp[i-1][j]
return dp[n][W]
weights = [2, 3, 4, 5]
values = [10, 20, 30, 40]
W = 8
print(knapsack(weights, values, W))  # Output: 60

5. Edit Distance (ED):

Find the edit distance between two strings.

def ed(s1, s2):
m, n = len(s1), len(s2)
dp = [[0] * (n + 1) for _ in range(m + 1)]
for i in range(m + 1):
for j in range(n + 1):
if i == 0:
dp[i][j] = j
elif j == 0:
dp[i][j] = i
elif s1[i-1] == s2[j-1]:
dp[i][j] = dp[i-1][j-1]
else:
dp[i][j] = 1 + min(dp[i-1][j], dp[i][j-1])
return dp[m][n]
s1 = "kite"
s2 = "bar"
print(ed(s1, s2))  # Output: 4

These are just a few examples of using dynamic programming in Python. The key idea is to break down the problem into smaller subproblems and solve them recursively or iteratively, using the solutions to the subproblems to construct the solution to the original problem.

Is there dynamic programming in Python?

I'd be happy to explain dynamic programming in the context of Python.

Dynamic programming is a method for solving complex problems by breaking them down into smaller subproblems. It's an essential concept in computer science and programming, and it's widely used in many areas, such as algorithms, artificial intelligence, and machine learning.

In Python, you can implement dynamic programming using various techniques, including memoization, tabulation, and recursion with memoization. Let me explain each of these approaches:

For example, consider the Fibonacci sequence problem: find the nth Fibonacci number. You can solve this using recursion, but it becomes inefficient for larger values of n because it recalculates many intermediate results. By using memoization, you can store these intermediate results and avoid redundant calculations:

def fibonacci(n, memo={}):
if n in memo:
return memo[n]
if n <= 1:
return n
result = fibonacci(n-1, memo) + fibonacci(n-2, memo)
memo[n] = result
return result

For example, consider the 0/1 knapsack problem: given a set of items, each with a weight and value, determine the subset that maximizes the total value while not exceeding a given capacity (knapsack). You can solve this using dynamic programming by filling up a table where each cell represents the maximum value for the subproblem:

def knapsack(weights, values, capacity):
dp = [[0] * (capacity + 1) for _ in range(len(weights) + 1)]
for i in range(1, len(weights) + 1):
for j in range(1, capacity + 1):
if weights[i-1] <= j:
dp[i][j] = max(values[i-1] + dp[i-1][j-weights[i-1]], dp[i-1][j])
else:
dp[i][j] = dp[i-1][j]
return dp[-1][-1]

For example, consider the longest common subsequence (LCS) problem: given two sequences, find their longest common subsequence. You can solve this using recursion with memoization:

def lcs(seq1, seq2):
@functools.lru_cache(maxsize=None)
def dp(i, j):
if i == 0 or j == 0:
return 0
if seq1[i-1] == seq2[j-1]:
return 1 + dp(i-1, j-1)
else:
return max(dp(i-1, j), dp(i, j-1))
return dp(len(seq1), len(seq2))

In summary, dynamic programming is a powerful technique for solving complex problems by breaking them down into smaller subproblems. Python provides various tools and techniques to implement dynamic programming, including memoization, tabulation, and recursion with memoization. By mastering these concepts, you can write efficient and effective algorithms that solve challenging problems.