1
2024年3月21日小于 1 分钟
背包问题可以大致分为三类,分别是:
其基础的背包问题一般由两个模型演变而来:
本文先研究 0-1 背包和完全背包,而后对其他问题进行研究。
问题 | 类型 | 递推公式 | 备注 |
---|---|---|---|
例题 LC474:1和0 | 0-1 背包最大最小值问题 | dp[i] = max(dp[i], dp[i-num] + 1) |
两个背包 |
例题 LC416:分割等和子集 | 0-1 背包True/False问题 | dp[i] = dp[i] or dp[i - num] |
|
例题 LC494:目标和 | 0-1 背包组合问题 | dp[i] += dp[i - num] |
|
例题 LC1049:最后一块石头的重量 III | 0-1 背包最大最小值问题 | dp[i] = max(dp[i], dp[i-stone] + stone) |
2024年9月9日更新:不要想那么多的模板,记住区间的开合关系即可,比如用左闭右开区间 [), 和 python 很像,则代码有几个注意点:
LCS 问题有很多的子问题,大致包括以下:
最长公共子串,要求子串在原字符串中是连续的
最长公共子序列
最大子序列
最长递增子序列
def LCSubStr(str1, str2, m, n):
LCSuff = [[0 for i in range(n + 1)] for j in range(m + 1)]
# 最长公共子串的长度
result = 0
# str1 中的最后相同的位置
p = 0
for i in range(m + 1):
for j in range(n + 1):
if(i == 0 or j == 0):
LCSuff[i][j] = 0
elif(str1[i - 1] == str2[j - 1]):
LCSuff[i][j] = LCSuff[i-1][j-1] + 1
result = max(result, LCSuff[i][j])
p = i
else:
LCSuff[i][j] = 0
return str1[p - result:p], result
X = 'OldSite:GeeksforGeeks.org'
Y = 'NewSite:GeeksQuiz.com'
m = len(X)
n = len(Y)
print('Length of Longest Common Substring is',
LCSubStr(X, Y, m, n))