基础算法精讲·题目汇总灵茶山艾府 - 【基础算法精讲】- GitHub视频灵茶山艾府的个人空间-灵茶山艾府个人主页-哔哩哔哩视频力扣最全 DP 题单分享丨【算法题单】动态规划入门/背包/划分/状态机/区间/状压/数位/树形/优化 - 讨论 - 力扣LeetCode21 状态机dp​课程讲解不限交易次数122. 买卖股票的最佳时机 II​​这种表示状态之间转换关系的图叫【状态机】​定义状态和状态转移方程​​​dfs(n-1, 1) 一定小于 dfs(n-1, 0)classSolution:defmaxProfit(self, prices:list[int]) -int: n len(prices)cachedefdfs(i, hold):ifi 0:return-infifholdelse0ifhold:returnmax(dfs(i-1,1), dfs(i-1,0) - prices[i])else:returnmax(dfs(i-1,0), dfs(i-1,1) prices[i])returndfs(n-1,0)时间复杂度状态个数 O(n) * 单个状态的计算时间 O(1)空间复杂度O(n)​classSolution:defmaxProfit(self, prices:list[int]) -int: n len(prices) f [[0] *2for_inrange(n1)] f[0][1] -inffori, pinenumerate(prices): f[i1][0] max(f[i][0], f[i][1] p) f[i1][1] max(f[i][1], f[i][0] - p)returnf[n][0]空间优化滚动计算classSolution:defmaxProfit(self, prices:list[int]) -int: n len(prices) f0 0f1 -infforpinprices: new_f0 max(f0, f1 p)# 一定要用一个临时变量先存储起来f1 max(f1, f0 - p) f0 new_f0returnf0空间复杂度 O(1)309. 买卖股票的最佳时机含冷冻期卖出后不能立刻买入股票。换句话说在买入股票的时候前一天不能有卖出股票的操作classSolution:defmaxProfit(self, prices:list[int]) -int: n len(prices)cachedefdfs(i, hold):ifi 0:return-infifholdelse0ifhold:returnmax(dfs(i-1,1), dfs(i-2,0) - prices[i])# 把i-1改成i-2即可else:returnmax(dfs(i-1,0), dfs(i-1,1) prices[i])returndfs(n-1,0)限制至多交易k次188. 买卖股票的最佳时机 IV​既然有次数限制就应当在递归的过程中去记录次数。因此在无限次交易的基础上增加一个参数 j表示至多完成 j 笔交易​classSolution:defmaxProfit(self, k:int, prices:List[int]) -int: n len(prices)cachedefdfs(i, j, hold):ifj 0:return-inf# 表示这是一个不合法的方案ifi 0:return-infifholdelse0ifhold:returnmax(dfs(i-1, j,1), dfs(i-1, j,0) - prices[i])else:returnmax(dfs(i-1, j,0), dfs(i-1, j-1,1) prices[i])# j-1表示增加一次交易次数returndfs(n-1, k,0)时空间复杂度都多了一个 k​classSolution:defmaxProfit(self, k:int, prices:List[int]) -int: n len(prices) f [[[-inf] *2for_inrange(k2)]for_inrange(n1)]# 初始化forjinrange(1, k2): f[0][j][0] 0fori, pinenumerate(prices):forjinrange(1, k2): f[i1][j][0] max(f[i][j][0], f[i][j-1][1] p) f[i1][j][1] max(f[i][j][1], f[i][j][0] - p)returnf[n][k1][0]空间优化优化到 O(k)f[i1] 只用到 f[i]所以这一维可以去掉由于 f[i1][j] 需要从 f[i][j-1] 转移过来j 改成倒序遍历由于 f[j][1] 会用到 f[j][0] 的结果而反过来是不需要的所以可以先计算 f[j][1]classSolution:defmaxProfit(self, k:int, prices:List[int]) -int: n len(prices) f [[-inf] *2for_inrange(k2)]# 初始化forjinrange(1, k2): f[j][0] 0fori, pinenumerate(prices):forjinrange(k1,0, -1): f[j][1] max(f[j][1], f[j][0] - p) f[j][0] max(f[j][0], f[j-1][1] p)returnf[k1][0]​恰好递归到 i0 时只有 j0 才是合法的j0 是不合法的# 恰好classSolution:defmaxProfit(self, k:int, prices:List[int]) -int:# 递推n len(prices) f [[[-inf] *2for_inrange(k 2)]for_inrange(n 1)] f[0][1][0] 0# 只需改这里fori, pinenumerate(prices):forjinrange(1, k 2): f[i 1][j][0] max(f[i][j][0], f[i][j][1] p) f[i 1][j][1] max(f[i][j][1], f[i][j -1][0] - p)returnf[-1][-1][0]# 记忆化搜索# cache# def dfs(i: int, j: int, hold: bool) - int:# if j 0:# return -inf# if i 0:# return -inf if hold or j 0 else 0# if hold:# return max(dfs(i - 1, j, True), dfs(i - 1, j - 1, False) - prices[i])# return max(dfs(i - 1, j, False), dfs(i - 1, j, True) prices[i])# return dfs(n - 1, k, False)至少递归到「至少 0 次」时它等价于「交易次数没有限制」那么这个状态的计算方式和122. 买卖股票的最佳时机 II是一样的# 至少classSolution:defmaxProfit(self, k:int, prices:List[int]) -int:# 递推n len(prices) f [[[-inf] *2for_inrange(k 1)]for_inrange(n 1)] f[0][0][0] 0fori, pinenumerate(prices): f[i 1][0][0] max(f[i][0][0], f[i][0][1] p) f[i 1][0][1] max(f[i][0][1], f[i][0][0] - p)# 无限次forjinrange(1, k 1): f[i 1][j][0] max(f[i][j][0], f[i][j][1] p) f[i 1][j][1] max(f[i][j][1], f[i][j -1][0] - p)returnf[-1][-1][0]# 记忆化搜索# cache# def dfs(i: int, j: int, hold: bool) - int:# if i 0:# return -inf if hold or j 0 else 0# if hold:# return max(dfs(i - 1, j, True), dfs(i - 1, j - 1, False) - prices[i])# return max(dfs(i - 1, j, False), dfs(i - 1, j, True) prices[i])# return dfs(n - 1, k, False)作者灵茶山艾府链接https://leetcode.cn/problems/best-time-to-buy-and-sell-stock-iv/solutions/2201488/shi-pin-jiao-ni-yi-bu-bu-si-kao-dong-tai-kksg/来源力扣LeetCode课后作业121. 买卖股票的最佳时机123. 买卖股票的最佳时机 III714. 买卖股票的最佳时机含手续费2826. 将三个组排序2786. 访问数组中的位置使分数最大1911. 最大子序列交替和22 区间dp​课程讲解516. 最长回文子序列​classSolution:# 最长公共子序列的代码deflongestCommonSubsequence(self, text1, text2): n len(text1) m len(text2) f [[0] * (m1)for_inrange(n1)]fori, xinenumerate(text1):forj, yinenumerate(text2):ifx y: f[i1][j1] f[i][j] 1else: f[i1][j1] max(f[i][j1], f[i1][j])returnf[n][m]deflongestPalindromeSubseq(self, s:str) -int:returnself.longestCommonSubsequence(s, s[::-1])​​​classSolution:deflongestPalindromeSubseq(self, s:str) -int: n len(s)cachedefdfs(i, j):ifi j:# 一个无效的字符串return0ifi j:return1ifs[i] s[j]:returndfs(i1, j-1) 2returnmax(dfs(i1, j), dfs(i, j-1))returndfs(0, n-1)时间复杂度状态有 O(n^2) 个每个状态只需要 O(1) 的时间计算空间复杂度状态个数 O(n^2)​classSolution:deflongestPalindromeSubseq(self, s:str) -int: n len(s) f [[0] * nfor_inrange(n)]foriinrange(n-1, -1, -1): f[i][i] 1forjinrange(i1, n):ifs[i] s[j]: f[i][j] f[i1][j-1] 2else: f[i][j] max(f[i1][j], f[i][j-1])returnf[0][n-1]1039. 多边形三角剖分的最低得分把一个 n 边形剖分成 n-2 个三角形​整个多边形的分数就是所有三角形的分数之和从其中的一条边开始思考​​​递归边界就是只有两个点的情况此时没有三角形返回0class Solution: def minScoreTriangulation(self, values: list[int]) - int: n len(values) cache def dfs(i, j): if i1 j: # 此时只有两个点不存在三角形 return 0 res inf for k in range(i1, j): res min(res, dfs(i, k) dfs(k, j) values[i] * values[j] * values[k]) return res return dfs(0, n-1)时间复杂度状态有 O(n^2) 个每个状态需要 O(n) 的时间来计算空间复杂度状态个数class Solution: def minScoreTriangulation(self, values: list[int]) - int: n len(values) f [[0] * n for _ in range(n)] # j至少要从i2开始所以i要从n-3开始倒序循环 for i in range(n-3, -1, -1): for j in range(i2, n): res inf for k in range(i1, j): res min(res, f[i][k] f[k][j] values[i] * values[j] * values[k]) f[i][j] res return f[0][n-1]课后作业1312. 让字符串成为回文串的最少插入次数3472. 至多 K 次操作后的最长回文子序列3040. 相同分数的最大操作数目 II1130. 叶值的最小代价生成树1770. 执行乘法运算的最大分数1771. 由子序列构造的最长回文串的长度1547. 切棍子的最小成本23 树形dp上树的直径课程讲解104. 二叉树的最大深度# Definition for a binary tree node. # class TreeNode: # def __init__(self, val0, leftNone, rightNone): # self.val val # self.left left # self.right right class Solution: def maxDepth(self, root: Optional[TreeNode]) - int: if root is None: return 0 left_depth self.maxDepth(root.left) right_depth self.maxDepth(root.right) return max(left_depth, right_depth) 1543. 二叉树的直径直径在这条树上找到一条最长的路径这里的路径长度定义为边的数目。那么这条路径的端点即起点和终点一定在叶子上子树最长链的计算方式和二叉树的最大深度是类似的# Definition for a binary tree node. # class TreeNode: # def __init__(self, val0, leftNone, rightNone): # self.val val # self.left left # self.right right class Solution: def diameterOfBinaryTree(self, root: Optional[TreeNode]) - int: ans 0 def dfs(node): if node is None: return -1 l_len dfs(node.left) r_len dfs(node.right) nonlocal ans ans max(ans, l_len r_len 2) return max(l_len, r_len) 1 dfs(root) return ans时间复杂度O(n)每个点都遍历一次空间复杂度O(n)最坏情况下这棵二叉树是一条链递归需要 O(n) 的栈空间124. 二叉树中的最大路径和注意节点值有负数负数返回0表示不选# Definition for a binary tree node. # class TreeNode: # def __init__(self, val0, leftNone, rightNone): # self.val val # self.left left # self.right right class Solution: def maxPathSum(self, root: TreeNode | None) - int: ans -inf # 由于节点值有负数且路径至少要有一个点 def dfs(node): if node is None: return 0 l_val dfs(node.left) r_val dfs(node.right) nonlocal ans ans max(ans, l_val r_val node.val) return max(max(l_val, r_val) node.val, 0) # 如果是负数就不选返回0 dfs(root) return ans时间复杂度O(n)空间复杂度O(n)2246. 相邻字符不同的最长路径一般树的直径引入一个邻居的概念如果两个点 x y 之间有边相连那么可以说x是y的邻居或y是x的邻居在二叉树中一个节点至多有三个邻居左儿子、右儿子、父节点而在一般树中邻居的个数就不定了需要用for循环去挨个遍历它的邻居求直径如果没有相邻节点的限制那么本题求的就是树的直径上的点的个数见 1245. 树的直径class Solution: def longestPath(self, parent: List[int], s: str) - int: # 边是以parent数组的形式给出的即从parent[i]到i有一条边 n len(parent) g [[] for _ in range(n)] for i in range(1, n): # 由于0是根节点这条边不存在所以从1开始遍历 g[parent[i]].append(i) # g[i]存储着第i个节点的邻居不包含父节点因为只有从parent[i]到i的边 ans 0 def dfs(x): nonlocal ans x_len 0 # x的最长链长初始化为0 for y in g[x]: # 遍历x的所有儿子 y_len dfs(y) 1 if s[y] ! s[x]: # 题目要求相邻节点不能有相同字符 ans max(ans, x_len y_len) x_len max(x_len, y_len) return x_len dfs(0) # 0是根节点 return ans 1 # 路径上点的数量 边的数量 1时间复杂度O(n)空间复杂度O(n)如果x的邻居包含父节点可以这样写class Solution: def longestPath(self, parent: List[int], s: str) - int: n len(parent) g [[] for _ in range(n)] for i in range(1, n): g[parent[i]].append(i) ans 0 def dfs(x, fa): # fa表示x的父节点 nonlocal ans x_len 0 for y in g[x]: if y fa: continue y_len dfs(y, x) 1 # x是y的父节点 if s[y] ! s[x]: ans max(ans, x_len y_len) x_len max(x_len, y_len) return x_len dfs(0, -1) # 0是根节点没有父节点因此传入-1 return ans 1课后作业687. 最长同值路径3203. 合并两棵树后的最小直径1617. 统计子树中城市之间最大距离2538. 最大价值和与最小价值和的差值24 树形dp中树上最大独立集课程讲解337. 打家劫舍 III选/不选时 这棵子树选的数的和最大是多少# Definition for a binary tree node. # class TreeNode: # def __init__(self, val0, leftNone, rightNone): # self.val val # self.left left # self.right right class Solution: def rob(self, root: TreeNode | None) - int: def dfs(node): if node is None: return 0, 0 l_rob, l_not_rob dfs(node.left) r_rob, r_not_rob dfs(node.right) rob l_not_rob r_not_rob node.val not_rob max(l_rob, l_not_rob) max(r_rob, r_not_rob) return rob, not_rob return max(dfs(root))时间复杂度每个节点只递归一次O(n)空间复杂度在最坏情况下这棵二叉树是一条链递归需要 O(n) 的栈空间没有上司的舞会总结树是图的一种特殊情况如果点权都是1那么算出来的就是最大独立集了课后作业1377. T 秒后青蛙的位置2646. 最小化旅行的价格总和25 树形dp下树上最小支配集课程讲解968. 监控二叉树在二叉树的一些节点上安装摄像头每个摄像头可以监控它自己所在的节点以及相邻的节点。至少要安装多少个摄像头才能把所有节点都覆盖到呢ps如果一个节点的父节点和儿子节点都安装了摄像头那它既可以是黄色节点也可以是红色节点分类讨论蓝色根节点已经装了摄像头那么儿子装不装摄像头都可以最后的1表示这棵子树的根节点装了摄像头黄色红色# Definition for a binary tree node. # class TreeNode: # def __init__(self, val0, leftNone, rightNone): # self.val val # self.left left # self.right right class Solution: def minCameraCover(self, root: Optional[TreeNode]) - int: def dfs(node): if node is None: return inf, 0, 0 l_choose, l_by_fa, l_by_childen dfs(node.left) # 递归左子树返回的三个值 r_choose, r_by_fa, r_by_childen dfs(node.right) # 该节点安装摄像头 choose min(l_choose, l_by_fa, l_by_childen) min(r_choose, r_by_fa, r_by_childen) 1 # 该节点没装其父节点监控到 by_fa min(l_choose, l_by_childen) min(r_choose, r_by_childen) # 该节点没装其儿子节点监控到 by_children min(l_chooser_by_childen, l_by_childenr_choose, l_chooser_choose) return choose, by_fa, by_children # 根节点没有父节点所以不用关心by_fa choose, _, by_children dfs(root) return min(choose, by_children)时间复杂度递归这棵二叉树每个节点都递归一次。O(n)空间复杂度最坏情况下这棵二叉树是一条链递归需要 O(n) 的栈空间变形1花费为cost968题LeetCode原题相当于每个节点的花费都是1只需要把代码里的 1 改成对应花费 cost[node] 就好了变形2一般树扩展到一般树的情况每个儿子蓝色or红色总共有 2^nn个儿子-1减去都是红色的情况红色节点要至少有一个蓝色的儿子如果去掉这个约束就只需要计算每个儿子是蓝色更小还是红色更小红色都比蓝色小的情况算出来不一样。如果要保证至少要选一个蓝色儿子可以把其中一个红色改成蓝色改一个蓝色减红色最小的儿子。如果说蓝色本来就是 ≤ 红色的就不用改了黄色式子不变红色式子可以化简在计算黄色公式的基础上增加一个蓝色减红色的最小值红色 黄色所以计算蓝色的公式也可以化简去掉红色保安站岗Python 代码 https://www.luogu.com.cn/paste/y9iiynzw课后作业LCP34. 二叉树染色LCP64. 二叉树灯饰