Dynamic Programming — Patterns (Part I)
Patterns and examples with solution
Part I | Part II | Part III | Part IV | Part V | Part VI
We will discuss the following three patterns.
- Fibonacci Sequence
- Longest common Subsequence
- Longest Increasing Subsequence
Fibonacci Sequence
The Fibonacci sequence pattern is useful when the solution to a problem depends on the solutions of smaller instances of the same problem.
class Solution:
def fib(self, n: int) -> int:
penultimate, last = 0, 1
if n <= 1:
return n
res = 0
for _ in range(2, n+1, 1):
res = penultimate + last
penultimate, last = last, res
return resTo reach some staircase n we can come from either n-1 stair or n-2 stair. So number of ways to reach at n = (No of ways to reach n-1 + number of ways to reach n-2).
DP with array
class Solution:
def climbStairs(self, n: int) -> int:
if n == 0:
return 0
if n == 1:
return 1
if n == 2:
return 2
dp = [0] * n
dp[0] = 1
dp[1] = 2
for i in range(2, n):
dp[i] = dp[i - 1] + dp[i - 2]
return dp[n - 1]DP without array, space optimization.
class Solution:
def climbStairs(self, n: int) -> int:
penultimate_step_count, last_step_count = 1, 2
if n <= 2:
return n
for _ in range(3, n+1, 1):
res = penultimate_step_count + last_step_count
penultimate_step_count, last_step_count = last_step_count, res
return resTo reach some staircase n we will have two options
- Option 1: Go there from staircase n-1. This will have a cost = (min cost to reach staircase n-1 + cost[n-1])
- Option 2: Go there from staircase n-2. This will have a cost = (min cost to reach staircase n-2 + cost[n-2])
The base case will be 0 for step 0 and 1.
DP with array solution.
class Solution:
def minCostClimbingStairs(self, cost: List[int]) -> int:
n = len(cost)
if n <=2:
return min(cost)
dp = [0] * (n+1)
dp[0] = 0
dp[1] = 0
for i in range(2, n+1):
option1 = dp[i-1] + cost[i-1]
option2 = dp[i-2] + cost[i-2]
dp[i] = min(option1, option2)
return dp[n]DP without array, space optimization.
class Solution:
def minCostClimbingStairs(self, cost: List[int]) -> int:
if len(cost) <=2:
return min(cost)
cost_for_penultimate_step, cost_for_last_step = 0, 0
res = 0
for i in range(2, len(cost) + 1):
res = min(cost_for_penultimate_step + cost[i-1], cost_for_last_step + cost[i-2])
cost_for_penultimate_step, cost_for_last_step = res, cost_for_penultimate_step
return resThe problem requires maximizing stolen money while avoiding adjacent houses. At each house, the robber faces a binary choice:
- Rob it: Add current house’s value to the maximum value from two houses prior (non-adjacent)
- Skip it: Carry forward the maximum value from the previous house
DP with array.
class Solution:
def rob(self, nums: List[int]) -> int:
size = len(nums)
if size < 3:
return max(nums)
dp = [0] * (size + 1)
dp[1], dp[2] = nums[0], nums[1]
for i in range(2, size):
dp[i+1] = max(dp[i-1], dp[i-2]) + nums[i]
return max(dp[-1], dp[-2])DP without array, space optimization.
class Solution:
def rob(self, nums: List[int]) -> int:
rob1, rob2 = 0, 0
for num in nums:
decision = max((num + rob1), rob2)
rob1, rob2 = rob2, decision
return rob2class Solution:
def rob(self, nums: List[int]) -> int:
if len(nums) == 1:
return nums[0]
def dp(nums):
not_rob_otay = [0]
res = [0]
for i in range(len(nums)):
not_rob_otay.append(res[-1])
res.append(max(not_rob_otay[-2] + nums[i], res[-1]))
return res[-1]
return max(dp(nums[1:]), dp(nums[:-1]))DP without array, space optimization
class Solution:
def rob(self, nums: List[int]) -> int:
n = len(nums)
if n <=2 :
return max(nums)
sum0 = nums[0]
sum1 = max(sum0, nums[1])
sum2 = sum1
for i in range(2, n-1):
sum2 = max(sum1, sum0 + nums[i])
sum0, sum1 = sum1, sum2
max_sum = sum2
sum0 = nums[1]
sum1 = max(sum0, nums[2])
sum2 = sum1
for i in range(3, n):
sum2 = max(sum1, sum0 + nums[i])
sum0, sum1 = sum1, sum2
return max(max_sum, sum2)Longest Common Subsequence
The Longest Common Subsequence pattern is useful when we are given two sequences and we need to find a subsequence that appears in the same order in both the given sequences.
This approach builds a 2D table where the entry at dp[i][j] represents the length of the LCS of the first i characters of the first string and the first j characters of the second string. The DP approach has a time complexity of O(m * n) and space complexity of O(m * n), making it much more efficient than the recursive approach.
Moving from the beginning:
- Compare characters if they match move both pointer (increment subsequence length by 1 as we have a match)
- If they don’t match, move one pointer and keep the other same, or move the other pointer and keep the one same. Take max of these two.
Code:
class Solution:
def longestCommonSubsequence(self, text1: str, text2: str) -> int:
m, n = len(text1), len(text2)
dp = [[0]*(n+1) for _ in range(m+1)]
for i in range(1, m+1):
for j in range(1, n+1):
if text1[i-1] == text2[j-1]:
dp[i][j] = 1 + dp[i-1][j-1]
else :
dp[i][j] = max(dp[i-1][j], dp[i][j-1])
return dp[m][n]Moving from end
class Solution:
def longestCommonSubsequence(self, text1: str, text2: str) -> int:
m, n = len(text1), len(text2)
dp = [[0]*(n+1) for _ in range(m+1)]
for i in range(m-1, -1, -1):
for j in range(n-1, -1, -1):
if text1[i] == text2[j]:
dp[i][j] = 1 + dp[i+1][j+1]
else :
dp[i][j] = max(dp[i+1][j], dp[i][j+1])
return dp[0][0]This is similar to the previous question. No of deletions we need to make is equal to no of items not matching. In other word, if we find the Longest common sequence and subtract that from both the array length we get the no of deletions needed.
Code
class Solution:
def minDistance(self, word1: str, word2: str) -> int:
m, n = len(word1), len(word2)
dp = [[0]*(n+1) for _ in range(m+1)]
for i in range(m-1, -1, -1):
for j in range(n-1, -1, -1):
if word1[i] == word2[j]:
dp[i][j] = 1 + dp[i+1][j+1]
else :
dp[i][j] = max(dp[i+1][j], dp[i][j+1])
lcs_len = dp[0][0]
return (m+n) - (2 * lcs_len)class Solution:
def shortestCommonSupersequence(self, str1: str, str2: str) -> str:
str1_length = len(str1)
str2_length = len(str2)
dp = [[0] * (str2_length + 1) for _ in range(str1_length + 1)]
for row in range(str1_length + 1):
dp[row][0] = row
for col in range(str2_length + 1):
dp[0][col] = col
for row in range(1, str1_length + 1):
for col in range(1, str2_length + 1):
if str1[row - 1] == str2[col - 1]:
dp[row][col] = dp[row - 1][col - 1] + 1
else:
dp[row][col] = min(dp[row - 1][col], dp[row][col - 1]) + 1
super_sequence = []
row, col = str1_length, str2_length
while row > 0 and col > 0:
if str1[row - 1] == str2[col - 1]:
super_sequence.append(str1[row - 1])
row -= 1
col -= 1
elif dp[row - 1][col] < dp[row][col - 1]:
super_sequence.append(str1[row - 1])
row -= 1
else:
super_sequence.append(str2[col - 1])
col -= 1
while row > 0:
super_sequence.append(str1[row - 1])
row -= 1
while col > 0:
super_sequence.append(str2[col - 1])
col -= 1
return "".join(super_sequence[::-1])Longest increasing subsequence
The Longest Increasing Subsequence pattern is used to solve problems that involve finding the longest subsequence of elements in a sequence where the elements are in increasing order.
The base case for the problem is 1 as each number can create a sequence of length 1. Now for each index, we can check how many numbers are smaller than the number at the index. In other words, we are trying to find the length of the sequence ending at the current index.
Code:
class Solution:
def lengthOfLIS(self, nums: List[int]) -> int:
n = len(nums)
dp = [1] * n
for i in range(n):
for j in range(i):
if nums[j] < nums[i]:
dp[i] = max(dp[i], dp[j] + 1)
return max(dp)Note: An alternative nlogn solution without dp using binary search
class Solution:
def lengthOfLIS(self, nums: List[int]) -> int:
from bisect import bisect_left
sub = []
for num in nums:
i = bisect_left(sub, num)
if i == len(sub):
sub.append(num)
else:
sub[i] = num
return len(sub)This is similar to the LIS question with one added constraint that the sequence should be strictly increasing.
class Solution:
def findNumberOfLIS(self, nums: List[int]) -> int:
n = len(nums)
dp = [1] * n
longest = [1] * n
for i in range(n):
for j in range(i):
if nums[j] < nums[i]:
if dp[j] + 1 > dp[i]:
longest[i] = longest[j]
dp[i] = dp[j] + 1
elif dp[j] + 1 == dp[i]:
longest[i] += longest[j]
max_length = max(dp)
return sum(longest[i] for i in range(n) if dp[i] == max_length)Can be optimized with Binary Index Tree.
class Solution:
def findLongestChain(self, pairs: List[List[int]]) -> int:
longest, n = 0, len(pairs)
dp = [1] * n
pairs.sort()
for i in range(n - 1, -1, -1):
for j in range(i + 1, n):
if pairs[i][1] < pairs[j][0]:
dp[i] = max(dp[i], dp[j] + 1)
longest = max(longest, dp[i])
return longestclass Solution:
def largestDivisibleSubset(self, nums: List[int]) -> List[int]:
if len(nums) == 0: return []
nums.sort()
dp = [[nums[i]] for i in range(len(nums))]
for i in range(len(dp)):
for j in range(i):
if nums[i] % nums[j] == 0 and len(dp[i]) < len(dp[j]) + 1:
dp[i] = dp[j] + [nums[i]]
return max(dp, key = len) class Solution:
def longestStrChain(self, words: List[str]) -> int:
'''
We iterate through words and use a hash map to hold the length of the longest chain ending with word w.
For each word w, we find all its possible predecessors, check if it is in the hash map and update dp[w].
'''
words.sort(key=len)
dp = {}
res = 1
for w in words:
dp[w] = 1
for i in range(len(w)):
predecessor = w[:i] + w[i+1:]
if predecessor in dp:
dp[w] = max(dp[w], dp[predecessor] + 1)
res = max(res, dp[w])
return res
class Solution:
def maxEnvelopes(self, envelopes: List[List[int]]) -> int:
envelopes.sort(key=lambda x: (x[0], -x[1]))
increasing = [envelopes[0][1]]
for i in range(1, len(envelopes)):
if increasing[-1] < envelopes[i][1]:
increasing.append(envelopes[i][1])
else:
left = 0
right = len(increasing)-1
while left < right:
mid = left + (right-left)//2
if increasing[mid] < envelopes[i][1]:
left = mid + 1
else:
right = mid
increasing[left] = envelopes[i][1]
return len(increasing)class Solution:
def minimumMountainRemovals(self, nums: List[int]) -> int:
n = len(nums)
# dp from front
dpf = [1] * n
for i in range(n - 1, -1, -1):
for j in range(i + 1, n):
if nums[i] > nums[j]:
dpf[i] = max(dpf[i], 1 + dpf[j])
# dp from back
dpb = [1] * n
for i in range(n):
for j in range(i - 1, -1, -1):
if nums[i] > nums[j]:
dpb[i] = max(dpb[i], 1 + dpb[j])
max_len = 0
for i in range(1, n - 1):
if dpf[i] > 1 and dpb[i] > 1:
max_len= max(dpf[i] + dpb[i] - 1, max_len)
return n - max_len
