声明：
算法基于https://labuladong.github.io/
python语言实现
53.maximum-subarray
72.edit-distance
494.target-sum
516. Longest Palindromic Subsequence
931.minimum-falling-path-sum
1143. Longest Common Subsequence
10.regular-expression-matching
53.maximum-subarray
from typing import List
class Solution:
def maxSubArray(self, nums: List[int]) -> int:
memory = dict()
def dp(i: int):
# base case
if i == 0:
memory[0] = nums[0]
return nums[0]
if memory.get(i): return memory[i]
# recursive
if nums[i - 1] > 0:
memory[i] = nums[i] + dp(i - 1)
else:
memory[i] = max(nums[i], nums[i] + dp(i - 1))
return memory[i]
max_subarr_len = 0
for i in range(len(nums)):
max_subarr_len = max(max_subarr_len, dp(i))
return max_subarr_len
def main():
# Input: nums = [-2,1,-3,4,-1,2,1,-5,4]
# Output: 6
# Explanation: [4,-1,2,1] has the largest sum = 6.
solution1 = Solution()
print(solution1.maxSubArray(nums=[-2, 1, -3, 4, -1, 2, 1, -5, 4]))
# Input: nums = [5,4,-1,7,8]
# Output: 23
solution1 = Solution()
print(solution1.maxSubArray(nums=[5, 4, -1, 7, 8]))
# Input: nums = [1]
# Output: 1
solution1 = Solution()
print(solution1.maxSubArray(nums=[1]))
if __name__ == '__main__':
main()
72.edit-distance
class Solution:
def minDistance(self, word1: str, word2: str) -> int:
memory = dict()
def dp(i: int, j: int) -> int:
# base case
if i == -1:
res = j + 1
return res
if j == -1:
res = i + 1
return res
# pre recursive:查memory
if memory.get((i, j)): return memory[(i, j)]
# recursive：结果写入memory
# 1.指针i，j所指字符相等时：
# i，j均前移一位，操作数（insert，delete，replace）不变
if word1[i] == word2[j]:
memory[(i, j)] = dp(i - 1, j - 1)
# 2.指针i，j所指字符不等时：
# 操作数加一，指针移动位数依照具体的操作
# dp(i, j - 1) + 1, # insert
# dp(i - 1, j) + 1, # delete
# dp(i - 1, j - 1) + 1 # replace
else:
memory[(i, j)] = min(
dp(i, j - 1) + 1,
dp(i - 1, j) + 1,
dp(i - 1, j - 1) + 1
)
# post recusive：返回memory[(i, j)]
return memory[(i, j)]
return dp(len(word1) - 1, len(word2) - 1)
def main():
# Input: word1 = "horse", word2 = "ros"
# Output: 3
# Explanation:
# horse -> rorse (replace 'h' with 'r')
# rorse -> rose (remove 'r')
# rose -> ros (remove 'e')
solution1 = Solution()
print(solution1.minDistance(word1="horse", word2="ros"))
# Input: word1 = "intention", word2 = "execution"
# Output: 5
# Explanation:
# intention -> inention (remove 't')
# inention -> enention (replace 'i' with 'e')
# enention -> exention (replace 'n' with 'x')
# exention -> exection (replace 'n' with 'c')
# exection -> execution (insert 'u')
solution2 = Solution()
print(solution2.minDistance(word1="intention", word2="execution"))
if __name__ == '__main__':
main()
494.target-sum
"""
本例含有重复子问题，需使用备忘录优化，原因如下：
【仅抽象出递归框架，查看不同状态转移之间的路径是否唯一】：唯一，不存在重叠子问题，无需备忘录
不唯一，存在重叠子问题，需使用备忘录去重
本题递归框架为：
def dp(i: int, target: int) -> int:
dp(i - 1, target - nums[i])
dp(i - 1, target + nums[i])
如果nums[i] = 0，这样就出现了两个「状态」完全相同的递归函数，无疑这样的递归计算就是重复的。
这就是重叠子问题，而且只要我们能够找到一个重叠子问题，那一定还存在很多的重叠子问题。
因此，状态 (i, remain) 是可以用备忘录技巧进行优化的：
！！！用Python的【哈希表dict】来做备忘录，其中dict的【key为dp方法所有入参组成的元组对：(dp_arg1, dp_arg2, ...)，即所有的可变状态的组合】
memory = dict()
{(dp_arg1_state1, dp_arg2_state2, ...):value1, (dp_arg1_state2, dp_arg2_state2, ...):value2, (dp_arg1_state3, dp_arg2_state3, ...):value3, ...}
"""
from typing import List
class Solution:
def findTargetSumWays(self, nums: List[int], target: int) -> int:
memory = dict()
def dp(i: int, target: int) -> int:
# base case
if i == 0:
if nums[i] == 0 and nums[i] == target:
return 2
elif nums[i] == target or -nums[i] == target:
return 1
else:
return 0
# pre recursive:查memory
# NOTE:需要把i和target的组合作为key，而不能仅把i作为key
# ！！！即需要把dp方法中所包含的所有可变状态的组合作为key！！！
if memory.get((i,target)): return memory[(i,target)]
# recursive:写memory
ways_add = dp(i - 1, target - nums[i])
ways_plus = dp(i - 1, target + nums[i])
memory[(i,target)] = ways_add + ways_plus
# post recursive:
return memory[(i,target)]
return dp(len(nums) - 1, target)
def main():
# Input: nums = [1,1,1,1,1], target = 3
# Output: 5
# Explanation: There are 5 ways to assign symbols to make the sum of nums be target 3.
# -1 + 1 + 1 + 1 + 1 = 3
# +1 - 1 + 1 + 1 + 1 = 3
# +1 + 1 - 1 + 1 + 1 = 3
# +1 + 1 + 1 - 1 + 1 = 3
# +1 + 1 + 1 + 1 - 1 = 3
solution1 = Solution()
print(solution1.findTargetSumWays(nums=[1, 1, 1, 1, 1], target=3))
# Input: nums = [1], target = 1
# Output: 1
solution2 = Solution()
print(solution2.findTargetSumWays(nums=[1], target=1))
# Input: [0,0,0,0,0,0,0,0,1] 1
# Output: 128
# Expected: 256
solution3 = Solution()
print(solution3.findTargetSumWays([0, 0, 0, 0, 0, 0, 0, 0, 1], 1))
if __name__ == '__main__':
main()
494.without_memo_Time-Limit-Error
class Solution:
def findTargetSumWays(self, nums: List[int], target: int) -> int:
def dp(i: int, target: int) -> int:
# base case
if i == 0:
if nums[i] == 0 and nums[i] == target:
return 2
elif nums[i] == target or -nums[i] == target:
return 1
else:
return 0
# recursive
ways_add = dp(i - 1, target - nums[i])
ways_plus = dp(i - 1, target + nums[i])
ways = ways_add + ways_plus
return ways
return dp(len(nums) - 1, target)
516. Longest Palindromic Subsequence
# 首尾指针i，j相向移动
# dp方法含义：返回子串s[i..j]的最长回文子序列的长度
class Solution:
def longestPalindromeSubseq(self, s: str) -> int:
n = len(s)
memo = [[0 for col in range(n)] for row in range(n)]
def dp(i: int, j: int) -> int:
# 递归出口
if i==j and s[i]==s[j]:return 1
elif i >= j: return 0
# pre recursive:查memo
if memo[i][j] != 0: return memo[i][j]
# 递归：写memo
if s[i] == s[j]:
memo[i][j] = dp(i + 1, j - 1) + 2
else:
memo[i][j] = max(dp(i + 1, j), dp(i, j - 1))
return memo[i][j]
return dp(0, len(s) - 1)
def main():
# Input: s = "bbbab"
# Output: 4
# Explanation: One possible longest palindromic subsequence is "bbbb".
solution1 = Solution()
print(solution1.longestPalindromeSubseq(s="bbbab"))
# Input: s = "cbbd"
# Output: 2
# Explanation: One possible longest palindromic subsequence is "bb".
solution2 = Solution()
print(solution2.longestPalindromeSubseq(s="cbbd"))
# Input "a"
# Output 0
# Expected 1
solution3 = Solution()
print(solution3.longestPalindromeSubseq(s="a"))
# Input "aaa"
# Output 2
# Expected 3
solution4 = Solution()
print(solution4.longestPalindromeSubseq(s="aaa"))
if __name__ == '__main__':
main()
931.minimum-falling-path-sum
from typing import List
class Solution:
def minFallingPathSum(self, matrix: List[List[int]]) -> int:
memory = dict()
n = len(matrix)
def dp(i: int, j: int) -> int:
# base case
if i == 0: return matrix[0][j]
# pre recursive:查memory
if memory.get((i, j)): return memory[(i, j)]
# recursive:写memory
if j == 0:
memory[(i, j)] = min(
dp(i - 1, j) + matrix[i][j],
dp(i - 1, j + 1) + matrix[i][j]
)
elif j == n - 1:
memory[(i, j)] = min(
dp(i - 1, j) + matrix[i][j],
dp(i - 1, j - 1) + matrix[i][j]
)
else:
memory[(i, j)] = min(
dp(i - 1, j - 1) + matrix[i][j],
dp(i - 1, j) + matrix[i][j],
dp(i - 1, j + 1) + matrix[i][j]
)
# post recursive:返回memory
return memory[(i, j)]
# 取j从0-n中最小的那个
min_sum = 99999999
for j in range(n):
# 递归部分从i=n-1减至0
min_sum = min(min_sum, dp(n - 1, j))
return min_sum
def main():
# Input: matrix = [[2,1,3],[6,5,4],[7,8,9]]
# Output: 13
# Explanation: There are two falling paths with a minimum sum as shown.
solution1 = Solution()
print(solution1.minFallingPathSum(matrix=[[2, 1, 3], [6, 5, 4], [7, 8, 9]]))
# Input: matrix = [[-19,57],[-40,-5]]
# Output: -59
# Explanation: The falling path with a minimum sum is shown.
solution2 = Solution()
print(solution2.minFallingPathSum(matrix=[[-19, 57], [-40, -5]]))
if __name__ == '__main__':
main()
1143. Longest Common Subsequence
class Solution:
def longestCommonSubsequence(self, text1: str, text2: str) -> int:
m = len(text1)
n = len(text2)
memo = [[0 for col in range(n)] for row in range(m)]
def dp(i: int, j: int) -> int:
# base case
if i == -1 or j == -1: return 0
# pre recursive：查memo
if memo[i][j] != 0: return memo[i][j]
# recursive
res = 0
if text1[i] == text2[j]:
res = dp(i - 1, j - 1) + 1
else:
res = max(dp(i - 1, j), dp(i, j - 1))
# post recursive: 写memo
memo[i][j] = res
return memo[i][j]
return dp(m - 1, n - 1)
def main():
# Input: text1 = "abcde", text2 = "ace"
# Output: 3
# Explanation: The longest common subsequence is "ace" and its length is 3.
solution1 = Solution()
print(solution1.longestCommonSubsequence(text1="abcde", text2="ace"))
# Input: text1 = "abc", text2 = "abc"
# Output: 3
# Explanation: The longest common subsequence is "abc" and its length is 3.
solution2 = Solution()
print(solution2.longestCommonSubsequence(text1="abc", text2="abc"))
# Input: text1 = "abc", text2 = "def"
# Output: 0
# Explanation: There is no such common subsequence, so the result is 0.
solution3 = Solution()
print(solution3.longestCommonSubsequence(text1="abc", text2="def"))
if __name__ == '__main__':
main()
10.regular-expression-matching
