Summary of Dynamic Programming IV.
LeetCode 300 Longest Increasing Subsequence
Define dp[i] the longest length of the subsequence considering the the part of sequence ended at nums[i]. The recurrence relation is if (nums[i] > nums[j]) dp[i] = max(dp[i], dp[j]+1). The base cases are for all i, dp[i]=1.
Time complexity O(n^2). Space complexity O(n).
class Solution:
def lengthOfLIS(self, nums: List[int]) -> int:
if len(nums) <= 1:
return len(nums)
dp = [1] * len(nums)
result = 0
for i in range(1, len(nums)):
for j in range(0, i):
if nums[j] < nums[i]:
dp[i] = max(dp[i], dp[j]+1)
result = max(result, dp[i])
return result
LeetCode 1143 Longest Common Subsequence
The subsequence is not necessarily continuous.
Define dp[i][j] as the length of longest common subsequence of text1 of length [0, i-1] and text2 of length [0, j-1]. If text1[i-1]=text2[j-1], we find a common element, then dp[i][j]=dp[i-1][j-1]+1. If text1[i-1]!=text2[j-1], we find the max of length of longest common subsequence of text1[i-2] and text2[j-1], and longest common subsequence of text1[i-1] and text2[j-2]. Then, dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]).
Base cases: dp[i][0]=dp[0][j]=0. Other values are initialized as zero as well.
Now the updating order is different from LC718. The dp table can be updated along the diagonal lines from the upper left to the down right (dp[i-1][j-1] -> dp[i][j]), and can also be updated from upper cell or left cell (dp[i-1][j]->dp[i][j] and dp[i][j-1]->dp[i][j]).
class Solution:
def longestCommonSubsequence(self, text1: str, text2: str) -> int:
dp = [[0]* (len(text2)+1) for _ in range(len(text1)+1)]
for i in range(1, len(text1)+1):
for j in range(1, len(text2)+1):
if text1[i-1] == text2[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[-1][-1]
LeetCode 1035 Uncrossed Lines
Time complexity O(nm). Space complexity O(nm).
class Solution:
def maxUncrossedLines(self, nums1: List[int], nums2: List[int]) -> int:
dp = [[0]*(len(nums2)+1) for _ in range(len(nums1)+1)]
for i in range(1, len(nums1) + 1):
for j in range(1, len(nums2) + 1):
if nums1[i-1] == nums2[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[-1][-1]
LeetCode 674 Longest Continuous Increasing Subsequence
Define dp[i] as the length of increasing subsequence ended with nums[i]. We don’t need to compare any nums[i] and nums[j] (j<i), instead, we need to compare nums[i+1] and nums[i].
class Solution:
def findLengthOfLCIS(self, nums: List[int]) -> int:
if len(nums) <= 1: return len(nums)
dp = [1] * len(nums)
result = 1
for i in range(1, len(nums)):
if nums[i] > nums[i-1]:
dp[i] = dp[i-1] + 1
result = max(result, dp[i])
return result
LeetCode 718 Maximum Length of Repeated Subarray
Define dp[i][j] as the length of the longest subsequence in both sequences nums1 and nums2 ended at i-1 and j-1. Both i and j start from 1. When nums1[i-1]=nums2[i-1], dp[i][j]=dp[i-1][j-1]+1.
Base cases: dp[0][j]=0 and dp[i][0]=0. dp[0][0]=0.
The dp table is updated along the diagonal lines from the upper left to the down right. dp[i-1][j-1] -> dp[i][j].
class Solution:
def findLength(self, nums1: List[int], nums2: List[int]) -> int:
dp = [[0] * (len(nums2)+1) for _ in range(len(nums1)+1)]
result = 0
for i in range(1, len(nums1)+1):
for j in range(1, len(nums2)+1):
if nums1[i-1] == nums2[j-1]:
dp[i][j] = dp[i-1][j-1] + 1
result = max(result, dp[i][j])
return result
LeetCode 53 Maximum Subarray
Define dp[i] as the max sum of the subsequence in the range of the [0,i] of the array. Suppose all numbers in nums are positive, when it comes to num[i], we add it to get larger sum, so we must have dp[i] = dp[i-1] + num[i]. However, any value in the num can be negative.
Case 1: dp[i-1] <= 0, including dp[i-1] won’t increase the sum, we have dp[i] = num[i].
Case 2: dp[i-1] > 0, including dp[i-1] will increase the sum, so we have dp[i] = dp[i-1] + num[i].
The function for DP is: max(nums[i], dp[i-1]+ nums[i]). If dp[i-1]+ nums[i] is smaller than nums[i], dp[i-1] has no contribution to the sum.
Time complexity O(n), space complexity O(n).
class Solution(object):
def maxSubArray(self, nums):
dp = [0]*(len(nums))
dp[0] = nums[0]
for i in range(1, len(nums)):
dp[i] = max(dp[i-1] + nums[i], nums[i])
return max(dp)
Use a rolling array to reduce space complexity to O(1). Time complexity is still O(n).
class Solution(object):
def maxSubArray(self, nums):
for i in range(1, len(nums)):
nums[i] += max(nums[i-1], 0)
return max(nums)
Reduced space using two variables:
class Solution(object):
def maxSubArray(self, nums):
res = nums[0]
cur = nums[0]
for i in nums[1:]:
cur = max(cur + n, n)
res = max(res, cur)
return res
LeetCode 392 Is Subsequence
A subsequence of a string is a new string that is formed from the original string by deleting some (can be none) of the characters without disturbing the relative positions of the remaining characters. (i.e., “ace” is a subsequence of “abcde” while “aec” is not).
Dynamic Programming. Define dp[i][j] as the length of common subsequence of s[0:i-1] and t[0:j-1]. (i-1 and j-1 because in this way we can leave room for initializing zeros at dp[i][0] and dp[0][j]). Case 1: if s[i - 1] == t[j - 1], then dp[i][j] = dp[i - 1][j - 1] + 1; Case 2: s[i - 1] != t[j - 1], then dp[i][j] = dp[i][j - 1].
Since updating dp[i][j] depends on dp[i-1][j-1] and dp[i][j-1], we need to initialize dp[0][0] and dp[i][0].
class Solution:
def isSubsequence(self, s: str, t: str) -> bool:
dp = [[0]*(len(t)+1) for _ in range(len(s)+1)]
for i in range(1, len(s)+1):
for j in range(1, len(t)+1):
if s[i-1] == t[j-1]:
dp[i][j] = dp[i-1][j-1]+1
else:
dp[i][j] = dp[i][j-1]
if dp[-1][-1] == len(s):
return True
return False
LeetCode 115 Distinct Subsequences
Define dp[i][j] as the number of t[0:j-1] appearing in s[0:i-1].
Case1: s[i-1] == t[j-1]. We can either use s[i-1] to match or not use s[i-1] to match. If we use s[i-1] to match, dp[i][j] = dp[i-1][j-1]. If we don’t use s[i-1] to match, dp[i][j] = dp[i-1][j]. So the total number of matches is dp[i][j] = dp[i-1][j-1] + dp[i-1][j].
Case2: s[i-1] != t[j-1]. We don’t use s[i-1] to match, then dp[i][j] = dp[i - 1][j].
We need to initialize dp[i][0] and dp[0][j]. dp[i][0]=1 because we can delete all characters from s[i] to get an empty string. dp[0][j]=0 because we can never get a t[j] from an empty string s.
Time complexity O(n^2). Space complexity O(n^2).
class Solution:
def numDistinct(self, s: str, t: str) -> int:
dp = [[0]*(len(t)+1) for _ in range(len(s)+1)]
for i in range(len(s)+1):
dp[i][0] = 1
for i in range(1,len(s)+1):
for j in range(1, len(t)+1):
if s[i-1] == t[j-1]:
dp[i][j] = dp[i-1][j-1] + dp[i-1][j]
else:
dp[i][j] = dp[i-1][j]
return dp[-1][-1]
LeetCode 583 Delete Operation for Two Strings
Define dp[i][j] as the minimum number of deletion of word1[0:i-1] and word2[0:j-1] to make them the same.
Case1: word1[i-1]==word2[j-1]. dp[i][j] = dp[i - 1][j - 1].
Case2: word1[i-1]!=word2[j-1]. dp[i][j] = min(dp[i-1][j]+1, dp[i][j-1]+1, dp[i - 1][j-1]+2).
Initialize dp[i][0] and dp[0][j]. dp[i][0]=i and dp[0][j]=j.
class Solution:
def minDistance(self, word1: str, word2: str) -> int:
dp = [[0]*(len(word2)+1) for _ in range(len(word1)+1)]
for i in range(len(word1)+1):
dp[i][0] = i
for j in range(len(word2)+1):
dp[0][j] = j
for i in range(1, len(word1)+1):
for j in range(1, len(word2)+1):
if word1[i-1] == word2[j-1]:
dp[i][j] = dp[i - 1][j - 1]
else:
dp[i][j] = min(dp[i-1][j]+1, dp[i][j-1]+1, dp[i - 1][j-1]+2)
return dp[-1][-1]
LeetCode 72 Edit Distance
Define dp[i][j] as the minimum number of editions of word1[0:i-1] and word2[0:j-1] to make them the same.
Case 1: word1[i-1]==word2[j-1]. We do nothing. dp[i][j] = dp[i - 1][j - 1].
Case 2: word1[i-1]!=word2[j-1]. We do insert, delete, or replace. dp[i][j] = min({dp[i - 1][j - 1], dp[i - 1][j], dp[i][j - 1]}) + 1.
The difference between LC72 and LC583 is that in LC72 we allow to replace a character so we don’t need to delete one character from both words.
class Solution:
def minDistance(self, word1: str, word2: str) -> int:
dp = [[0]*(len(word2)+1) for _ in range(len(word1)+1)]
for i in range(len(word1)+1):
dp[i][0] = i
for j in range(len(word2)+1):
dp[0][j] = j
for i in range(1, len(word1)+1):
for j in range(1, len(word2)+1):
if word1[i-1] == word2[j-1]:
dp[i][j] = dp[i-1][j-1]
else:
dp[i][j] = min(dp[i-1][j]+1, dp[i][j-1]+1, dp[i-1][j-1]+1)
return dp[-1][-1]
LeetCode 647 Palindromic Substrings
Define dp[i][j] as (True of False) whether [i,j] is a palindromic string.
Case1: s[i] != s[j], dp[i][j] = False.
Case2: s[i] == s[j], if i=j, dp[i][j] = True; if i-j = +-1, dp[i][j] = True ; if i-j > 1 or i-j < -1, dp[i][j] = dp[i+1][i-1].
Initialization: dp[i][j] = False.
Because dp[i+1][j-1] is on the left bottom of dp[i][j]，the outer loop is iterating from the bottom to the top, and the inner loop is iterating from the left to the right.
class Solution:
def countSubstrings(self, s: str) -> int:
dp = [[False] * len(s) for _ in range(len(s))]
res = 0
for i in range(len(s)-1, -1, -1):
for j in range(i, len(s)):
if s[i] == s[j]:
if j - i <= 1:
res += 1
dp[i][j] = True
elif dp[i+1][j-1]:
res += 1
dp[i][j] = True
return res
LeetCode 516 Longest Palindromic Subsequence
Define dp[i][j] as the longest length of the palindromic subsequence in s[i,j].
Case1: s[i] != s[j], only add s[i] or add s[j] see whether it can form a longer palindromic sequence. Therefore, dp[i][j] = max(dp[i + 1][j], dp[i][j - 1]).
Case2: s[i] == s[j], dp[i][j] = dp[i + 1][j - 1] + 2.
Initialization: if i=j, then the longest palindromic subsequence is of length 1. dp[i][j]=1. If i!=j, then dp[i][j]=0.
class Solution:
def longestPalindromeSubseq(self, s: str) -> int:
dp = [[0] * len(s) for _ in range(len(s))]
for i in range(len(s)):
dp[i][i] = 1
for i in range(len(s)-1, -1, -1):
for j in range(i+1, len(s)):
if s[i] == s[j]:
dp[i][j] = dp[i+1][j-1] + 2
else:
dp[i][j] = max(dp[i+1][j], dp[i][j-1])
return dp[0][-1]
