Part 3 – Two Sequences Dynamic Programming
这类题目是动态规划乃至全LeetCode题目当中最难的题目，4个主要元素完全不固定，递推量和递推式都要因题而异而且不好确定。但做多了还是有些许规律可循的，大部分是针对字符串处理的动态规划题目，理清s字符串第i个字符和p字符串第j个字符之间的关系即可。
1）确定递推量。res[i][j]表示第一个字符串前i个字符配上第二个字符串前j个字符的状态；
2）推导递推式。res[i][j]一般研究第i个字符和第j个字符的匹配关系；
3）计算初始条件。res[i][0]/res[0][i]；
4）考虑存储历史信息的空间维度（可选）。一般就是一维空间，不可优化。
1143. Longest Common Subsequence
https://leetcode-cn.com/problems/longest-common-subsequence/
res[i][j]表示前i个字符配上前j个字符的LCS长度。递推式即循环体内容，比较容易理解。注意这里建了一个长度为(m+1)*(n+1)的二维数组，方便计算，最后返回res[m][n]即可。
代码如下：
class Solution:
"""
@param A: A string
@param B: A string
@return: The length of longest common subsequence of A and B
"""
def longestCommonSubsequence(self, A, B):
m = len(A)
n = len(B)
res = [[0 for j in range(n + 1)] for i in range(m + 1)]
for i in range(m):
for j in range(n):
if A[i] == B[j]:
res[i + 1][j + 1] = res[i][j] + 1
else:
res[i + 1][j + 1] = max(res[i + 1][j], res[i][j + 1])
return res[m][n]
Lint79. Longest Common Substring
https://www.lintcode.com/problem/longest-common-substring/description
res[i][j]表示前i个字符配上前j个字符的LCS’的长度（一定以第i个和第j个字符结尾的LCS’），结果max也需要一直更新。
代码如下：
class Solution:
"""
@param A: A string
@param B: A string
@return: the length of the longest common substring.
"""
def longestCommonSubstring(self, A, B):
m = len(A)
n = len(B)
res = [[0 for j in range(n + 1)] for i in range(m + 1)]
max_value = 0
for i in range(m):
for j in range(n):
if A[i] == B[j]:
res[i + 1][j + 1] = res[i][j] + 1
else:
res[i + 1][j + 1] = 0
max_value = max(max_value, res[i + 1][j + 1])
return max_value
72. Edit Distance
https://leetcode.com/problems/edit-distance/description/
res[i][j]表示word1的前i个字符配上word2的前j个字符最少要用几次编辑使得他们相等。优先使用二维空间稳定版，有能力再使用一维空间优化版。
代码如下：
class Solution:
def minDistance(self, word1, word2):
"""
:type word1: str
:type word2: str
:rtype: int
"""
m = len(word1)
n = len(word2)
res = [[0 for n in range(n + 1)] for i in range(m + 1)]
for i in range(m + 1):
res[i][0] = i
for j in range(n + 1):
res[0][j] = j
for i in range(m):
for j in range(n):
if word1[i] == word2[j]:
res[i + 1][j + 1] = res[i][j]
else:
res[i + 1][j + 1] = min(res[i + 1][j], res[i][j + 1], res[i][j]) + 1
return res[m][n]
class Solution:
def minDistance(self, word1, word2):
"""
:type word1: str
:type word2: str
:rtype: int
"""
m = len(word1)
n = len(word2)
if m < n:
return self.minDistance(word2, word1)
res = list(range(n + 1))
for i in range(m):
newRes = [0] * (n + 1)
newRes[0] = i + 1
for j in range(n):
if word1[i] == word2[j]:
newRes[j + 1] = res[j]
else:
newRes[j + 1] = min(res[j], res[j + 1], newRes[j]) + 1
res = newRes
return res[n]
115. Distinct Subsequences
https://leetcode.com/problems/distinct-subsequences/description/
res[i][j]表示S的前i个字符和T的前j个字符有多少个可行的序列。假设S的第i个字符和T的第j个字符不相同，那么就意味着res[i][j]的值和res[i - 1][j]的值相同，前面该是多少还是多少，而第i个字符的加入也不会多出来任何可行结果。如果S的第i个字符和T的第j个字符相同，那么所有res[i - 1][j - 1]中满足的结果都会成为新的满足的序列，当然res[i - 1][j]的也仍是可行的结果。算法进行两层循环，时间复杂度为O(m * n)，空间复杂度O(m)。优先使用稳定版，有能力再使用优化版。
代码如下：
class Solution:
def numDistinct(self, s, t):
"""
:type s: str
:type t: str
:rtype: int
"""
m = len(s)
n = len(t)
res = [[0 for j in range(n + 1)] for i in range(m + 1)]
for i in range(m + 1):
res[i][0] = 1
for i in range(m):
for j in range(n):
if s[i] == t[j]:
res[i + 1][j + 1] = res[i][j] + res[i][j + 1]
else:
res[i + 1][j + 1] = res[i][j + 1]
return res[m][n]
代码如下：
class Solution:
def numDistinct(self, s, t):
"""
:type s: str
:type t: str
:rtype: int
"""
m = len(s)
n = len(t)
res = [0] * (n + 1)
res[0] = 1
for i in range(m):
for j in range(n)[::-1]:
res[j + 1] += res[j] if s[i] == t[j] else 0
return res[n]
97. Interleaving String
https://leetcode.com/problems/interleaving-string/description/
res[i][j]表示用s1的前i个字符和s2的前j个字符能不能按照规则表示出前s3的前i+j个字符。优先使用稳定版，有能力再使用优化版。
代码如下：
class Solution:
def isInterleave(self, s1, s2, s3):
"""
:type s1: str
:type s2: str
:type s3: str
:rtype: bool
"""
m = len(s1)
n = len(s2)
if m + n != len(s3):
return False
res = [[False for j in range(n + 1)] for i in range(m + 1)]
res[0][0] = True
for i in range(m):
res[i + 1][0] = res[i][0] and s1[i] == s3[i]
for j in range(n):
res[0][j + 1] = res[0][j] and s2[j] == s3[j]
for i in range(m):
for j in range(n):
res[i + 1][j + 1] = res[i][j + 1] and s1[i] == s3[i + j + 1] or res[i + 1][j] and s2[j] == s3[i + j + 1]
return res[m][n]
class Solution:
def isInterleave(self, s1, s2, s3):
"""
:type s1: str
:type s2: str
:type s3: str
:rtype: bool
"""
m = len(s1)
n = len(s2)
if m + n != len(s3):
return False
if m < n:
return self.isInterleave(s2, s1, s3)
res = [False] * (n + 1)
res[0] = True
for i in range(n):
res[i + 1] = res[i] and s2[i] == s3[i]
for i in range(m):
res[0] = res[0] and s1[i] == s3[i]
for j in range(n):
res[j + 1] = res[j + 1] and s1[i] == s3[i + j + 1] or res[j] and s2[j] == s3[i + j + 1]
return res[n]
网友评论