一维DP数组问题
解题模板
# 一维DP数组
# dp[i]为以nums[i]为结尾的目标子序列长度
for i in range(len(nums)):
for j in range(i):
dp[i] = 最值(dp[i],dp[j] + ...)最长递增子序列（中等）
class Solution:
def lengthOfLIS(self, nums: List[int]) -> int:
if nums == []: return 0
m = len(nums)
dp = [1 for i in range(m)] # 以nums[i]为结尾的最长递增子序列
for i in range(1,m):
for j in range(i):
if nums[i] > nums[j]:
dp[i] = max(dp[i],dp[j]+1)
return max(dp)更快的方法：纸牌游戏
# 二分查找——纸牌游戏
class Solution:
def lengthOfLIS(self, nums: List[int]) -> int:
top = [] # 牌堆顶
for n in nums:
# 二分找左边界
left,right = 0,len(top)
while left < right:
mid = left + (right -left) // 2
if top[mid] == n:
right = mid
elif top[mid] < n:
left = mid + 1
elif top[mid] > n:
right = mid
if left == len(top): # 没找到,建新堆
top.append(n)
else:
top[left] = n
return len(top)二维DP数组问题
解题模板
# 二维DP数组
# 1. dp[i][j]为s1[0...i-1]和s2[0...j-1]中的目标子序列（最长公共子序列、编辑距离）
# 2. dp[i][j]为s[i...j]中的目标子序列（最长回文子序列）
m,n = len(s1),len(s2)
dp = [[0 for j in range(n+1)] for i in range(m+1)]
... # 处理 base case
for i in range(1,m+1):
for j in range(1,n+1):
if s1[i-1] == s2[j-1]:
dp[i][j] = dp[i-1][j-1] + ...
else:
dp[i][j] = 最值(...)最长公共子序列（中等）
class Solution:
def longestCommonSubsequence(self, text1: str, text2: str) -> int:
m,n = len(text1),len(text2)
# dp[i][j] text1[0...i-1]和text2[0...j-1]最长公共子序列
dp = [[0 for j in range(n+1)] for i in range(m+1)]
# basecase d[0][0] dp[0][1] dp[1][0] = 0
for i in range(1,m+1):
for j in range(1,n+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]