-
Notifications
You must be signed in to change notification settings - Fork 2
Dynamic Programming Problems
Praveen Kumar Anwla edited this page Dec 27, 2024
·
59 revisions
Ans:
**DP[i][j] = exlude_item or include_item::**
The line combines two scenarios using the logical **`or`** operator:
#### **1. Excluding the Current Element (`DP[i - 1][j]`):**
- If we **exclude** the current element `nums[i]`, the ability to achieve the sum `j` depends entirely on whether we could achieve the sum `j` using the first `i-1` elements.
- This is represented by `DP[i - 1][j]`.
#### **2. Including the Current Element (`DP[i - 1][j - nums[i]]`):**
- If we **include** the current element `nums[i]`, then:
- The remaining sum to achieve becomes `j - nums[i]`.
- We check whether this reduced sum (`j - nums[i]`) could be achieved using the first `i-1` elements.
- This is represented by `DP[i - 1][j - nums[i]]`.
#### **Combining the Two Scenarios:**
- The line `DP[i][j] = DP[i - 1][j] or DP[i - 1][j - nums[i]]` means:
- `DP[i][j]` will be `True` if **either**:
1. The sum `j` was already achievable without the current element (`DP[i - 1][j] = True`), OR
2. The sum `j` becomes achievable by including the current element (`DP[i - 1][j - nums[i]] = True`).
---
### **Why This Works:**
This line uses the principle of **inclusion-exclusion**:
- If the subset sum `j` can be formed **without** the current element (`DP[i - 1][j]`), we don't need to include it.
- If the subset sum `j` can be formed by including the current element (`DP[i - 1][j - nums[i]]`), then it contributes to the solution.
This ensures that all possible subsets involving the first `i` elements are considered when determining whether the sum `j` is achievable.
# Check DP[i][j] = exlude_item or include_item:
# exlude_item : It was possible to achieve the sum j without the current number (DP[i - 1][j]).
# include_item: It was possible to achieve the reduced sum i.e. j - nums[i - 1] with the current number (DP[i - 1][j - nums[i - 1]]).
def subset_sum(M, nums):
# Initialize the DP table
DP = [[False for _ in range(M + 1)] for _ in range(len(nums))]
# Initialize the first column to True (sum 0 is always achievable)
for i in range(len(nums)):
DP[i][0] = True
# Fill the DP table
for i in range(1, len(nums)): # Start from 1 since nums[0] = 0 is just a placeholder
for j in range(1, M + 1):
if nums[i] <= j: #If the current number is less than the local sum value.
exlude_item = DP[i - 1][j] # Copy the value from above cell. Since, the subset sum j can be achieved without including the current number (nums[i]). Therefore, simply copy the value from the above cell.
include_item = DP[i - 1][j - nums[i]] # We check whether this reduced sum (`j - nums[i]`) could be achieved using the first `i-1` elements.
DP[i][j] = exlude_item or include_item
else: #If the current number is greater than the local sum
DP[i][j] = exlude_item # # Don't include the item in subset; Copy the value from above cell. Since after adding the current item also local sum will be less than subset combined.
# Check if a subset with the desired sum exists
if not DP[len(nums) - 1][M]:
print("No subset with the given sum exists.")
return
# Backtrack to find the elements in the subset
print("Subset with the given sum:")
j = M
i = len(nums) - 1
while i > 0 and j > 0:
if DP[i][j] != DP[i - 1][j]: # If current cell doesn't matche the cell above, the current number is included
print('item for the subset: %d' % nums[i])
j -= nums[i]
# Move to next line
i -= 1
# Example input
M = 12
nums = [0, 1, 2, 4, 6]
subset_sum(M, nums)Ans:
def longest_common_subseq(s1, s2):
DP = [[0 for _ in range(len(s1)+1)] for _ in range(len(s2)+1)]
# This is why Running time complexity = o(m*n)
# m= len(s1), n= len(s2)
# Construct the table
for i in range(1, len(s1)+1):
for j in range(1, len(s2)+1):
# NOte: we're comparing s1[i - 1] & s2[j - 1] at both times
# 1)while creating a memoization table and while backtracking
# coz we've appended 0 in both strings. Hence, i-1 to compare current elements.
if s1[i-1] == s2[j-1]: # if chars are matching
DP[i][j] = DP[i-1][j-1]+1 #length of the LCS at DP[i][j] is 1 more than the LCS of the strings without these characters, which is DP[i-1][j-1].
else: #We take the best possible answer so far, which is the maximum of:
# DP[i-1][j]: LCS if we ignore the current character of s1.
# DP[i][j-1]: LCS if we ignore the current character of s2.
DP[i][j] = max(DP[i-1][j], DP[i][j-1])
# Retrieve the longest common subsequence
lcs = ''
i, j = len(s1), len(s2)
while i > 0 or j > 0:
if s1[i-1] == s2[j-1]: # if chars are matching then char is part of lcs
lcs += s1[i-1]
# Got to diagonal cell
i -= 1
j -= 1
# if chars are not matching then find larger of 2 cells and go one step in direction of larger one
elif DP[i-1][j] > DP[i][j-1]: # top cell value > left cell value
i -= 1 # go up
else: # left cell value > top cell value
j -= 1 # go left
return print(lcs[::-1])
s1 = "ABCD"
s2 = "ACDF"
longest_common_subseq(s1, s2)Ans:
def rod_cutting(length, Profits):
DP = [[0]*(length+1) for _ in range(len(Profits))]
# Construct the table
for i in range(1, len(Profits)): # starting_range=1 coz 0 is the base
for j in range(1, length+1):
if i <= j: # if current piece length is less than or equal to the length of the rod
DP[i][j] = max(DP[i-1][j], Profits[i]+DP[i][j-i]) ## DP[i-1][j] : excluding current piece
else: # if current piece length is greater than length of the rod, meaning you can't make the cut. Hence, exclude current piece.
DP[i][j] = DP[i-1][j]
i = len(Profits)-1
j = length
while i > 0 or j > 0:
if DP[i][j] != DP[i-1][j]: ## # if current and top cells are not matching then take this ; meaning current item is in solution. print("Take piece with length:", i, "meter")
j -= i
else: #if current and top cells are matching then given item is not in solution.
print("Take piece with length:", i, "meter")
i -= 1
# Example input
length = 5
Profits = [0, 2, 5, 7, 3, 9]
# Call the function
rod_cutting(length , Profits)Output:
- Take piece with length: 2 meter
- Take piece with length: 2 meter
- Take piece with length: 1 meter
Q4. 0/1 Knapsack Problem: you're given a set of items, each with a weight and a value, and your goal is to determine the combination of items to include in a knapsack of limited capacity such that the total value is maximized.
Ans:
def knapsack_prob(M, W, V):
N = len(W)-1
DP = [[0 for _ in range(M+1)] for _ in range(len(W))]
for i in range(1, len(W)): #For each item i, we have two choices: not_taking_item , taking_item
for j in range(1, M+1):
not_taking_item = DP[i-1][j] # The best value we can have is simply the best value we had without this item, i.e., DP[i-1][w].
taking_item = 0
if W[i] <= j: # Check if current item's weight is less than knapsack's capacity
taking_item = V[i] + DP[i-1][j-W[i]] # value if taking current item;
DP[i][j] = max(not_taking_item, taking_item) # Update DP table
else:
DP[i][j] = not_taking_item
print("Total benefit: %d" % DP[N][M])
j = M
for i in range(len(W)-1, 0 , -1): # Iterate through all items in DP table in backward direction
# If current weight is not zero, and current and above cell values are not matching
if DP[i][j] != 0 and DP[i][j] != DP[i-1][j]:
print("We're taking item #%d" % i)
j = j-W[i] # Decrease the knapsack's capacity, since we've considered this item already
# Example input
knapsack_capacity = 7
weights = [0, 1, 3, 4, 5]
profits = [0, 1, 4, 5, 7]
# Call the function
knapsack_prob(knapsack_capacity, weights, profits)output:
- Total benefit: 9
- We're taking item #3
- We're taking item #2
Q5: Kadane's Algorithm : Find Maximum consecutive Subarray i.e. Find the consecutive numbers of the array such that sum is the largest possible.
Ans:
# O(N)
def kadane(nums):
local_max = nums[0]
global_max = nums[0]
# this is why it has linear running time complexity
for i in range(1, len(nums)):
local_max = max(nums[i], local_max + nums[i])
if local_max > global_max:
global_max = local_max
return global_max
kadane([1, -2, 1, 2, 3, -4])Ans:
# top-down approach
def fibonacci_memoization(n, DP):
if n not in DP:
DP[n] = fibonacci_memoization(n-1, DP) + fibonacci_memoization(n-2, DP)
return DP[n]
# bottom-up approach
def fibonacci_tabulation(n, DP):
for i in range(2, n+1):
DP[i] = DP[i-1] + DP[i-2]
return DP[n]
DP = {0: 1, 1: 1}
print("===== fibonacci_tabulation =====")
print(fibonacci_tabulation(4, DP))
# print("===== fibonacci_memoization =====")
# print(fibonacci_memoization(4, DP))Q7. Search for occurrences of a pattern within a given text. The primary goal is to find all occurrences of a specified pattern in the text using "Knuth–Morris–Pratt (KMP) algorithm.
Ans:
def prepare_pi_table(pattern):
pi_table = [0] * len(pattern)
prefix_counter, i = 0, 1 # i: to iterate through elements of pattern
while i < len(pattern):
if pattern[i] == pattern[prefix_counter]:
pi_table[i] = prefix_counter + 1
i += 1
prefix_counter += 1
else:
if prefix_counter != 0:
prefix_counter = pi_table[prefix_counter - 1]
else:
pi_table[i] = 0
i += 1
return pi_table
def search_for_pattern(text, pattern):
pi_table = prepare_pi_table(pattern)
# i: to track elements in text, j: to track elements in pattern
i, j = 0, 0
while i < len(text) and j < len(pattern):
if text[i] == pattern[j]: # if chars in text and pattern match
i += 1
j += 1
# We found the pattern in the text( + reinitialize the jth index to be able to find more pattern)
# i-j because subtracting j after matching whole pattern i.e. last index of pattern from i i.e. index after matching complete pattern would give us starting position of pattern match in text
if j == len(pattern): # means if pattern's length is covered then pattern found
print('Pattern found at index %s' % (i - j))
j = pi_table[j - 1]
elif j != 0:
j = pi_table[j - 1]
else:
i += 1
# Example usage
search_for_pattern('abababab', 'aba')output:
- Pattern found at index 0
- Pattern found at index 2
- Pattern found at index 4