70.爬楼梯
🎭 题目小剧场
想象你在爬楼梯，每次可以爬1级或2级。要到达第n级台阶，有多少种不同的爬法？就像选择不同的路径到达山顶，每一步的选择都会影响最终的结果！
💡 解题思路
动态规划解法：
确定状态：dp[i] 表示到达第i级台阶的方法数
状态转移：dp[i] = dp[i-1] + dp[i-2]
初始条件：dp[0] = 1, dp[1] = 1
空间优化：只保留前两个状态
🐍 Python代码实现
class Solution: def climbStairs(self, n: int) -> int: """ 动态规划解法（空间优化） - 时间复杂度O(n)，空间复杂度O(1) """ if n <= 2: return n # dp[i-2] 和 dp[i-1] prev2, prev1 = 1, 2 for i in range(3, n + 1): current = prev1 + prev2 prev2, prev1 = prev1, current return prev1
📊 复杂度分析
时间复杂度：O(n) - 只需要遍历一次
空间复杂度：O(1) - 只使用常数额外空间
🌟 算法精髓
这个算法的巧妙之处在于"状态压缩"。我们不需要存储所有中间结果，只需要保留前两个状态就能计算出当前状态，大大节省了空间。
🎯 小白友好贴士
if n <= 2: return n 处理边界情况
prev2, prev1 = 1, 2 初始化前两个状态
current = prev1 + prev2 计算当前状态
prev2, prev1 = prev1, current 更新状态
return prev1 返回最终结果
🔍 算法执行过程示例
示例：n = 4初始：prev2 = 1, prev1 = 2第1步：i = 3 current = prev1 + prev2 = 2 + 1 = 3 prev2, prev1 = prev1, current = 2, 3第2步：i = 4 current = prev1 + prev2 = 3 + 2 = 5 prev2, prev1 = prev1, current = 3, 5结束：return prev1 = 5 ✅验证： 第1级：[1] → 1种方法 第2级：[1+1, 2] → 2种方法 第3级：[1+1+1, 1+2, 2+1] → 3种方法 第4级：[1+1+1+1, 1+1+2, 1+2+1, 2+1+1, 2+2] → 5种方法
🎯 核心思想总结
状态定义：明确dp数组的含义
状态转移：找到递推关系
初始条件：确定边界值
空间优化：减少不必要的存储
118.杨辉三角
🎭 题目小剧场
想象你在构建一个数字金字塔，每个数字都是它"肩膀"上两个数字的和。这个美丽的数学图案不仅看起来优雅，还隐藏着组合数学的奥秘！
💡 解题思路
动态规划解法：
初始化结果列表，第一行是[1]
从第二行开始，每行的首尾都是1
中间的数字等于上一行相邻两个数字之和
逐行构建直到第n行
🐍 Python代码实现
class Solution: def generate(self, numRows: int) -> List[List[int]]: """ 动态规划解法 - 时间复杂度O(n²)，空间复杂度O(n²) """ if numRows <= 0: return [] result = [] for row_num in range(numRows): # 创建当前行 row = [1] * (row_num + 1) # 计算中间的数字 for j in range(1, row_num): row[j] = result[row_num - 1][j - 1] + result[row_num - 1][j] result.append(row) return result
📊 复杂度分析
🌟 算法精髓
这个算法的巧妙之处在于"逐层构建"。我们利用杨辉三角的递推性质，每一行都基于上一行来构建，避免了复杂的组合计算。
🎯 小白友好贴士
if numRows <= 0: return [] 处理边界情况
row = [1] * (row_num + 1) 创建当前行并初始化为1
for j in range(1, row_num) 只计算中间位置
row[j] = result[row_num - 1][j - 1] + result[row_num - 1][j] 递推公式
result.append(row) 将当前行加入结果
🔍 算法执行过程示例
示例：numRows = 5初始：result = []第1行：row_num = 0 row = [1] * 1 = [1] result = [[1]]第2行：row_num = 1 row = [1] * 2 = [1, 1] result = [[1], [1, 1]]第3行：row_num = 2 row = [1] * 3 = [1, 1, 1] j = 1: row[1] = result[1][0] + result[1][1] = 1 + 1 = 2 row = [1, 2, 1] result = [[1], [1, 1], [1, 2, 1]]第4行：row_num = 3 row = [1] * 4 = [1, 1, 1, 1] j = 1: row[1] = result[2][0] + result[2][1] = 1 + 2 = 3 j = 2: row[2] = result[2][1] + result[2][2] = 2 + 1 = 3 row = [1, 3, 3, 1] result = [[1], [1, 1], [1, 2, 1], [1, 3, 3, 1]]第5行：row_num = 4 row = [1] * 5 = [1, 1, 1, 1, 1] j = 1: row[1] = result[3][0] + result[3][1] = 1 + 3 = 4 j = 2: row[2] = result[3][1] + result[3][2] = 3 + 3 = 6 j = 3: row[3] = result[3][2] + result[3][3] = 3 + 1 = 4 row = [1, 4, 6, 4, 1] result = [[1], [1, 1], [1, 2, 1], [1, 3, 3, 1], [1, 4, 6, 4, 1]]结束：return result ✅
🎯 核心思想总结
递推关系：每个数字等于上方两个数字之和
边界条件：每行的首尾都是1
逐层构建：从上到下逐行生成
空间利用：利用已生成的行来构建新行
198.打家劫舍
🎭 题目小剧场
想象你是一个神偷，在一条街上作案，但不能抢相邻的两家，因为会触发警报。你需要规划一条路线，在不触发警报的情况下，偷到最多的钱！
💡 解题思路
动态规划解法：
确定状态：dp[i] 表示到第i家能偷到的最大金额
状态转移：dp[i] = max(dp[i-1], dp[i-2] + nums[i])
初始条件：dp[0] = nums[0], dp[1] = max(nums[0], nums[1])
空间优化：只保留前两个状态
🐍 Python代码实现
class Solution: def rob(self, nums: List[int]) -> int: """ 动态规划解法（空间优化） - 时间复杂度O(n)，空间复杂度O(1) """ if not nums: return 0 if len(nums) == 1: return nums[0] # dp[i-2] 和 dp[i-1] prev2, prev1 = nums[0], max(nums[0], nums[1]) for i in range(2, len(nums)): # 当前状态：不偷当前家 vs 偷当前家 current = max(prev1, prev2 + nums[i]) prev2, prev1 = prev1, current return prev1
📊 复杂度分析
时间复杂度：O(n) - 只需要遍历一次
空间复杂度：O(1) - 只使用常数额外空间
🌟 算法精髓
这个算法的巧妙之处在于"状态压缩"。我们不需要存储所有中间结果，只需要保留前两个状态就能计算出当前状态，大大节省了空间。
🎯 小白友好贴士
if not nums: return 0 处理空数组
if len(nums) == 1: return nums[0] 处理单元素
prev2, prev1 = nums[0], max(nums[0], nums[1]) 初始化前两个状态
current = max(prev1, prev2 + nums[i]) 状态转移方程
prev2, prev1 = prev1, current 更新状态
🔍 算法执行过程示例
示例：nums = [2, 7, 9, 3, 1]初始：prev2 = 2, prev1 = max(2, 7) = 7第1步：i = 2, nums[2] = 9 current = max(prev1, prev2 + nums[2]) = max(7, 2 + 9) = 11 prev2, prev1 = prev1, current = 7, 11第2步：i = 3, nums[3] = 3 current = max(prev1, prev2 + nums[3]) = max(11, 7 + 3) = 11 prev2, prev1 = prev1, current = 11, 11第3步：i = 4, nums[4] = 1 current = max(prev1, prev2 + nums[4]) = max(11, 11 + 1) = 12 prev2, prev1 = prev1, current = 11, 12结束：return prev1 = 12 ✅验证： 选择第1、3、5家：2 + 9 + 1 = 12 选择第2、4家：7 + 3 = 10 最优解：12
🎯 核心思想总结
状态定义：明确dp数组的含义
状态转移：找到递推关系
初始条件：确定边界值
空间优化：减少不必要的存储
279.完全平方数
🎭 题目小剧场
想象你有一堆不同大小的正方形积木（1×1, 2×2, 3×3...），你想用最少数量的积木拼出一个给定的正方形。就像玩俄罗斯方块，要用最少的方块填满整个区域！
💡 解题思路
动态规划解法：
确定状态：dp[i] 表示组成数字i所需的最少完全平方数数量
状态转移：dp[i] = min(dp[i - jj] + 1)，其中jj ≤ i
初始条件：dp[0] = 0，其他初始化为无穷大
逐步计算从1到n的所有状态
🐍 Python代码实现
class Solution: def numSquares(self, n: int) -> int: """ 动态规划解法 - 时间复杂度O(n√n)，空间复杂度O(n) """ # dp[i] 表示组成数字i所需的最少完全平方数数量 dp = [float('inf')] * (n + 1) dp[0] = 0 # 0需要0个完全平方数 # 预计算所有可能的完全平方数 squares = [] i = 1 while i * i <= n: squares.append(i * i) i += 1 # 动态规划计算 for i in range(1, n + 1): for square in squares: if square > i: break dp[i] = min(dp[i], dp[i - square] + 1) return dp[n]
📊 复杂度分析
🌟 算法精髓
这个算法的巧妙之处在于"分解思想"。将复杂问题分解为子问题，通过子问题的最优解来构建原问题的最优解。
🎯 小白友好贴士
dp = [float('inf')] * (n + 1) 初始化dp数组
dp[0] = 0 设置初始条件
while i * i <= n 预计算完全平方数
dp[i] = min(dp[i], dp[i - square] + 1) 状态转移方程
return dp[n] 返回最终结果
🔍 算法执行过程示例
示例：n = 12第1步：预计算完全平方数 squares = [1, 4, 9]第2步：动态规划计算初始：dp = [0, inf, inf, inf, inf, inf, inf, inf, inf, inf, inf, inf, inf] i = 1: square = 1: dp[1] = min(inf, dp[0] + 1) = 1 square = 4: break (4 > 1) dp = [0, 1, inf, inf, inf, inf, inf, inf, inf, inf, inf, inf, inf] i = 2: square = 1: dp[2] = min(inf, dp[1] + 1) = 2 square = 4: break (4 > 2) dp = [0, 1, 2, inf, inf, inf, inf, inf, inf, inf, inf, inf, inf] i = 3: square = 1: dp[3] = min(inf, dp[2] + 1) = 3 square = 4: break (4 > 3) dp = [0, 1, 2, 3, inf, inf, inf, inf, inf, inf, inf, inf, inf] i = 4: square = 1: dp[4] = min(inf, dp[3] + 1) = 4 square = 4: dp[4] = min(4, dp[0] + 1) = 1 dp = [0, 1, 2, 3, 1, inf, inf, inf, inf, inf, inf, inf, inf] i = 5: square = 1: dp[5] = min(inf, dp[4] + 1) = 2 square = 4: dp[5] = min(2, dp[1] + 1) = 2 square = 9: break (9 > 5) dp = [0, 1, 2, 3, 1, 2, inf, inf, inf, inf, inf, inf, inf]... i = 12: square = 1: dp[12] = min(inf, dp[11] + 1) = 4 square = 4: dp[12] = min(4, dp[8] + 1) = 3 square = 9: dp[12] = min(3, dp[3] + 1) = 3 dp = [0, 1, 2, 3, 1, 2, 3, 4, 2, 1, 2, 3, 3]结束：return dp[12] = 3 ✅验证：12 = 4 + 4 + 4 (3个完全平方数)
🎯 核心思想总结
状态定义：明确dp数组的含义
状态转移：找到递推关系
初始条件：确定边界值
逐步计算：从小到大计算所有状态
322.零钱兑换
🎭 题目小剧场
想象你在自动售货机前，需要用最少的硬币买到饮料。机器里有不同面值的硬币，你需要计算如何组合这些硬币，正好凑齐商品价格，而且用的硬币数量最少！
💡 解题思路
动态规划解法：
确定状态：dp[i] 表示凑齐金额i所需的最少硬币数量
状态转移：dp[i] = min(dp[i - coin] + 1)，遍历所有硬币面值
初始条件：dp[0] = 0，其他初始化为无穷大
逐步计算从1到amount的所有状态
🐍 Python代码实现
class Solution: def coinChange(self, coins: List[int], amount: int) -> int: """ 动态规划解法 - 时间复杂度O(n×amount)，空间复杂度O(amount) """ if amount < 0: return -1 # dp[i] 表示凑齐金额i所需的最少硬币数量 dp = [float('inf')] * (amount + 1) dp[0] = 0 # 凑齐0金额需要0个硬币 # 动态规划计算 for i in range(1, amount + 1): for coin in coins: if coin <= i: dp[i] = min(dp[i], dp[i - coin] + 1) return dp[amount] if dp[amount] != float('inf') else -1
📊 复杂度分析
🌟 算法精髓
这个算法的巧妙之处在于"最优子结构"。每个金额的最优解都依赖于更小金额的最优解，通过这种递推关系，我们可以逐步构建出最终答案。
🎯 小白友好贴士
dp = [float('inf')] * (amount + 1) 初始化dp数组
dp[0] = 0 设置初始条件
for coin in coins 遍历所有硬币面值
if coin <= i 确保硬币面值不超过当前金额
dp[i] = min(dp[i], dp[i - coin] + 1) 状态转移方程
return dp[amount] if dp[amount] != float('inf') else -1 处理无解情况
🔍 算法执行过程示例
示例：coins = [1, 3, 4], amount = 6初始：dp = [0, inf, inf, inf, inf, inf, inf]第1步：i = 1 coin = 1: dp[1] = min(inf, dp[0] + 1) = 1 coin = 3: 3 > 1, 跳过 coin = 4: 4 > 1, 跳过 dp = [0, 1, inf, inf, inf, inf, inf]第2步：i = 2 coin = 1: dp[2] = min(inf, dp[1] + 1) = 2 coin = 3: 3 > 2, 跳过 coin = 4: 4 > 2, 跳过 dp = [0, 1, 2, inf, inf, inf, inf]第3步：i = 3 coin = 1: dp[3] = min(inf, dp[2] + 1) = 3 coin = 3: dp[3] = min(3, dp[0] + 1) = 1 coin = 4: 4 > 3, 跳过 dp = [0, 1, 2, 1, inf, inf, inf]第4步：i = 4 coin = 1: dp[4] = min(inf, dp[3] + 1) = 2 coin = 3: dp[4] = min(2, dp[1] + 1) = 2 coin = 4: dp[4] = min(2, dp[0] + 1) = 1 dp = [0, 1, 2, 1, 1, inf, inf]第5步：i = 5 coin = 1: dp[5] = min(inf, dp[4] + 1) = 2 coin = 3: dp[5] = min(2, dp[2] + 1) = 2 coin = 4: dp[5] = min(2, dp[1] + 1) = 2 dp = [0, 1, 2, 1, 1, 2, inf]第6步：i = 6 coin = 1: dp[6] = min(inf, dp[5] + 1) = 3 coin = 3: dp[6] = min(3, dp[3] + 1) = 2 coin = 4: dp[6] = min(2, dp[2] + 1) = 2 dp = [0, 1, 2, 1, 1, 2, 2]结束：return dp[6] = 2 ✅验证：6 = 3 + 3 (2个硬币) 或 6 = 4 + 1 + 1 (3个硬币)最优解：2个硬币
🎯 核心思想总结
状态定义：明确dp数组的含义
状态转移：找到递推关系
初始条件：确定边界值
无解处理：处理无法凑齐的情况
139.单词拆分
🎭 题目小剧场
想象你在玩拼字游戏，有一堆单词卡片，需要判断能否用这些卡片拼出给定的句子。就像用乐高积木搭建模型，每个积木都要严丝合缝地拼接在一起！
💡 解题思路
动态规划解法：
确定状态：dp[i] 表示字符串前i个字符是否可以被拆分
状态转移：dp[i] = dp[j] && s[j:i] in wordSet，其中0 ≤ j < i
初始条件：dp[0] = True（空字符串可以被拆分）
逐步计算从1到n的所有状态
🐍 Python代码实现
class Solution: def wordBreak(self, s: str, wordDict: List[str]) -> bool: """ 动态规划解法 - 时间复杂度O(n²)，空间复杂度O(n) """ word_set = set(wordDict) # 转换为集合，提高查找效率 n = len(s) dp = [False] * (n + 1) dp[0] = True # 空字符串可以被拆分 for i in range(1, n + 1): for j in range(i): if dp[j] and s[j:i] in word_set: dp[i] = True break return dp[n]
📊 复杂度分析
🌟 算法精髓
这个算法的巧妙之处在于"分段验证"。我们不直接判断整个字符串，而是将其分解为前缀和后缀，通过动态规划的方式逐步验证每个前缀是否可被拆分。
🎯 小白友好贴士
word_set = set(wordDict) 转换为集合，提高查找效率
dp = [False] * (n + 1) 初始化dp数组
dp[0] = True 设置初始条件
for j in range(i) 遍历所有可能的分割点
if dp[j] and s[j:i] in word_set 状态转移条件
dp[i] = True 标记当前位置可被拆分
break 找到一个有效分割即可
🔍 算法执行过程示例
示例：s = "leetcode", wordDict = ["leet", "code"]初始：word_set = {"leet", "code"}, n = 8dp = [True, False, False, False, False, False, False, False, False]第1步：i = 1, s[0:1] = "l" j = 0: dp[0] = True, "l" not in word_set dp[1] = False第2步：i = 2, s[0:2] = "le" j = 0: dp[0] = True, "le" not in word_set j = 1: dp[1] = False, 跳过 dp[2] = False第3步：i = 3, s[0:3] = "lee" j = 0: dp[0] = True, "lee" not in word_set j = 1: dp[1] = False, 跳过 j = 2: dp[2] = False, 跳过 dp[3] = False第4步：i = 4, s[0:4] = "leet" j = 0: dp[0] = True, "leet" in word_set ✓ dp[4] = True, break第5步：i = 5, s[0:5] = "leetc" j = 0: dp[0] = True, "leetc" not in word_set j = 1: dp[1] = False, 跳过 j = 2: dp[2] = False, 跳过 j = 3: dp[3] = False, 跳过 j = 4: dp[4] = True, "c" not in word_set dp[5] = False第6步：i = 6, s[0:6] = "leetco" j = 0: dp[0] = True, "leetco" not in word_set j = 1: dp[1] = False, 跳过 ... j = 4: dp[4] = True, "co" not in word_set j = 5: dp[5] = False, 跳过 dp[6] = False第7步：i = 7, s[0:7] = "leetcod" j = 0: dp[0] = True, "leetcod" not in word_set ... j = 4: dp[4] = True, "cod" not in word_set j = 5: dp[5] = False, 跳过 j = 6: dp[6] = False, 跳过 dp[7] = False第8步：i = 8, s[0:8] = "leetcode" j = 0: dp[0] = True, "leetcode" not in word_set j = 1: dp[1] = False, 跳过 ... j = 4: dp[4] = True, "code" in word_set ✓ dp[8] = True, break 结束：return dp[8] = True ✅
🎯 核心思想总结
状态定义：明确dp数组的含义
状态转移：找到递推关系
初始条件：确定边界值
分段验证：逐步验证每个前缀
300.最长递增子序列
🎭 题目小剧场
想象你在玩一个抽牌游戏，每次抽一张牌，你要按顺序摆放，要求后面的牌比前面的大。你想知道最多能摆出多长的递增序列。就像排队，要求后面的人比前面的人高，找出最长的可能队伍！
💡 解题思路
贪心 + 二分查找解法：
维护一个数组 tails，其中 tails[i] 表示长度为 i+1 的递增子序列的最小末尾元素
遍历每个数字，用二分查找在 tails 中找到合适的位置
如果数字比 tails 中所有元素都大，追加到末尾
否则，替换 tails 中第一个大于等于它的元素
最终 tails 的长度就是最长递增子序列的长度
🐍 Python代码实现
class Solution: def lengthOfLIS(self, nums: List[int]) -> int: """ 贪心 + 二分查找解法 - 时间复杂度O(n log n)，空间复杂度O(n) """ if not nums: return 0 tails = [] for num in nums: # 二分查找插入位置 left, right = 0, len(tails) while left < right: mid = (left + right) // 2 if tails[mid] < num: left = mid + 1 else: right = mid # 如果left等于tails长度，说明num比所有元素都大 if left == len(tails): tails.append(num) else: tails[left] = num return len(tails)
📊 复杂度分析
🌟 算法精髓
这个算法的巧妙之处在于"贪心维护"。我们维护的 tails 数组并不是真实的最长递增子序列，但它保证了在相同长度下，末尾元素是最小的，这样为后续元素提供了最大的扩展空间。
🎯 小白友好贴士
if not nums: return 0 处理空数组
tails = [] 初始化辅助数组
while left < right 二分查找模板
if tails[mid] < num 判断移动方向
if left == len(tails) 判断是否需要追加
tails[left] = num 替换对应位置元素
return len(tails) 返回最终长度
🔍 算法执行过程示例
示例：nums = [10, 9, 2, 5, 3, 7, 101, 18]初始：tails = []第1步：num = 10 二分查找：left = 0, right = 0 left == len(tails) (0 == 0) ✓ tails = [10]第2步：num = 9 二分查找： left = 0, right = 1, mid = 0 tails[0] = 10 >= 9, right = 0 left = 0, right = 0, 结束 left != len(tails) (0 != 1) ✗ tails[0] = 9 tails = [9]第3步：num = 2 二分查找： left = 0, right = 1, mid = 0 tails[0] = 9 >= 2, right = 0 left = 0, right = 0, 结束 left != len(tails) (0 != 1) ✗ tails[0] = 2 tails = [2]第4步：num = 5 二分查找： left = 0, right = 1, mid = 0 tails[0] = 2 < 5, left = 1 left = 1, right = 1, 结束 left == len(tails) (1 == 1) ✓ tails.append(5) tails = [2, 5]第5步：num = 3 二分查找： left = 0, right = 2, mid = 1 tails[1] = 5 >= 3, right = 1 left = 0, right = 1, mid = 0 tails[0] = 2 < 3, left = 1 left = 1, right = 1, 结束 left != len(tails) (1 != 2) ✗ tails[1] = 3 tails = [2, 3]第6步：num = 7 二分查找： left = 0, right = 2, mid = 1 tails[1] = 3 < 7, left = 2 left = 2, right = 2, 结束 left == len(tails) (2 == 2) ✓ tails.append(7) tails = [2, 3, 7]第7步：num = 101 二分查找： left = 0, right = 3, mid = 1 tails[1] = 3 < 101, left = 2 left = 2, right = 3, mid = 2 tails[2] = 7 < 101, left = 3 left = 3, right = 3, 结束 left == len(tails) (3 == 3) ✓ tails.append(101) tails = [2, 3, 7, 101]第8步：num = 18 二分查找： left = 0, right = 4, mid = 2 tails[2] = 7 < 18, left = 3 left = 3, right = 4, mid = 3 tails[3] = 101 >= 18, right = 3 left = 3, right = 3, 结束 left != len(tails) (3 != 4) ✗ tails[3] = 18 tails = [2, 3, 7, 18]结束：return len(tails) = 4 ✅验证：最长递增子序列为 [2, 3, 7, 18] 或 [2, 3, 7, 101]
🎯 核心思想总结
贪心策略：维护尽可能小的末尾元素
二分查找：快速找到插入位置
动态维护：不断更新tails数组
长度即答案：tails长度就是LIS长度
152.乘积最大子数组
🎭 题目小剧场
想象你在玩一个数字连连看游戏，每个数字都有正负，你要找出一段连续的数字，让它们的乘积最大。就像在股市中寻找最佳买入卖出点，需要考虑涨跌的相互影响！
💡 解题思路
动态规划解法：
确定状态：同时维护当前最大值和最小值
状态转移：遇到负数时，最大值和最小值会互换
初始条件：第一个数字既是最大值也是最小值
逐步计算并更新全局最大值
🐍 Python代码实现
class Solution: def maxProduct(self, nums: List[int]) -> int: """ 动态规划解法 - 时间复杂度O(n)，空间复杂度O(1) """ if not nums: return 0 # 维护当前最大值和最小值 current_max = current_min = result = nums[0] for i in range(1, len(nums)): num = nums[i] # 如果当前数字是负数，最大值和最小值会互换 if num < 0: current_max, current_min = current_min, current_max # 更新当前最大值和最小值 current_max = max(num, current_max * num) current_min = min(num, current_min * num) # 更新全局最大值 result = max(result, current_max) return result
📊 复杂度分析
时间复杂度：O(n) - 只需要遍历一次
空间复杂度：O(1) - 只使用常数额外空间
🌟 算法精髓
这个算法的巧妙之处在于"双重维护"。我们不仅维护最大值，还维护最小值，因为负数会反转大小关系，最小值乘以负数可能变成最大值。
🎯 小白友好贴士
if not nums: return 0 处理空数组
current_max = current_min = result = nums[0] 初始化状态
if num < 0 处理负数情况
current_max, current_min = current_min, current_max 交换最大最小值
current_max = max(num, current_max * num) 更新最大值
current_min = min(num, current_min * num) 更新最小值
result = max(result, current_max) 更新全局最大值
🔍 算法执行过程示例
示例：nums = [2, 3, -2, 4]初始：current_max = current_min = result = 2第1步：num = 3 num > 0，不需要交换 current_max = max(3, 2 * 3) = 6 current_min = min(3, 2 * 3) = 3 result = max(2, 6) = 6第2步：num = -2 num < 0，交换最大最小值 current_max, current_min = current_min, current_max = 3, 6 current_max = max(-2, 3 * -2) = -2 current_min = min(-2, 6 * -2) = -12 result = max(6, -2) = 6第3步：num = 4 num > 0，不需要交换 current_max = max(4, -2 * 4) = 4 current_min = min(4, -12 * 4) = -48 result = max(6, 4) = 6结束：return result = 6 ✅验证：最大乘积子数组为 [2, 3]，乘积为 6
🎯 核心思想总结
双重维护：同时维护最大值和最小值
负数处理：遇到负数时交换最大最小值
状态转移：考虑选择当前数字或延续之前的乘积
全局更新：每步都更新全局最大值
416.分割等和子集
🎭 题目小剧场
想象你有一堆不同重量的砝码，要放在天平的两边，让天平完美平衡。你需要判断是否可能将这些砝码分成两组，使两组的总重量完全相等！
💡 解题思路
动态规划解法（0-1背包问题）：
问题转化：判断能否从数组中选出若干数，使其和等于总和的一半
确定状态：dp[i] 表示能否凑出和为i
状态转移：dp[i] = dp[i] or dp[i - num]
遍历顺序：从后往前遍历，确保每个元素只使用一次
🐍 Python代码实现
class Solution: def canPartition(self, nums: List[int]) -> bool: """ 动态规划解法 - 时间复杂度O(n×target)，空间复杂度O(target) """ total_sum = sum(nums) # 如果总和为奇数，无法分割 if total_sum % 2 != 0: return False target = total_sum // 2 # dp[i] 表示能否凑出和为i dp = [False] * (target + 1) dp[0] = True # 和为0总是可以（不选任何元素） for num in nums: # 从后往前遍历，避免重复使用 for i in range(target, num - 1, -1): dp[i] = dp[i] or dp[i - num] return dp[target]
📊 复杂度分析
🌟 算法精髓
这个算法的巧妙之处在于"问题转化"。将分割问题转化为0-1背包问题，用动态规划求解子集和的可能性，从而判断是否能够等分。
🎯 小白友好贴士
total_sum = sum(nums) 计算数组总和
if total_sum % 2 != 0 奇数总和直接返回False
target = total_sum // 2 计算目标和
dp = [False] * (target + 1) 初始化dp数组
dp[0] = True 和为0总是可以
for i in range(target, num - 1, -1) 逆序遍历
dp[i] = dp[i] or dp[i - num] 状态转移方程
🔍 算法执行过程示例
示例：nums = [1, 5, 11, 5]初始：total_sum = 22, target = 11dp = [True, False, False, False, False, False, False, False, False, False, False, False]第1步：num = 1 i从11到1： i = 11: dp[11] = dp[11] or dp[10] = False or False = False i = 10: dp[10] = dp[10] or dp[9] = False or False = False ... i = 1: dp[1] = dp[1] or dp[0] = False or True = True dp = [True, True, False, False, False, False, False, False, False, False, False, False]第2步：num = 5 i从11到5： i = 11: dp[11] = dp[11] or dp[6] = False or False = False i = 10: dp[10] = dp[10] or dp[5] = False or False = False i = 9: dp[9] = dp[9] or dp[4] = False or False = False i = 8: dp[8] = dp[8] or dp[3] = False or False = False i = 7: dp[7] = dp[7] or dp[2] = False or False = False i = 6: dp[6] = dp[6] or dp[1] = False or True = True i = 5: dp[5] = dp[5] or dp[0] = False or True = True dp = [True, True, False, False, False, True, True, False, False, False, False, False]第3步：num = 11 i从11到11： i = 11: dp[11] = dp[11] or dp[0] = False or True = True dp = [True, True, False, False, False, True, True, False, False, False, False, True]第4步：num = 5 i从11到5： i = 11: dp[11] = dp[11] or dp[6] = True or True = True i = 10: dp[10] = dp[10] or dp[5] = False or True = True i = 9: dp[9] = dp[9] or dp[4] = False or False = False i = 8: dp[8] = dp[8] or dp[3] = False or False = False i = 7: dp[7] = dp[7] or dp[2] = False or False = False i = 6: dp[6] = dp[6] or dp[1] = True or True = True i = 5: dp[5] = dp[5] or dp[0] = True or True = True dp = [True, True, False, False, False, True, True, False, False, False, True, True]结束：return dp[11] = True ✅验证：可以分割为 [1, 5, 5] 和 [11]，和都为11
🎯 核心思想总结
问题转化：将分割问题转化为子集和问题
状态定义：明确dp数组的含义
状态转移：找到递推关系
逆序遍历：确保每个元素只使用一次
32.最长有效括号
🎭 题目小剧场
想象你在玩一个配对游戏，有一堆左括号 ( 和右括号 )，你要找出最长的连续序列，让它们都能完美配对。就像玩连连看，需要找到最长的有效连线！
💡 解题思路
栈 + 动态规划解法：
使用栈记录括号的位置，栈底保存最后一个未匹配的右括号位置
遇到左括号时，将其位置入栈
遇到右括号时，弹出栈顶元素
如果栈为空，说明当前右括号无法匹配，将其位置入栈
如果栈不为空，计算当前有效长度：i - stack[-1]
维护最大长度
🐍 Python代码实现
class Solution: def longestValidParentheses(self, s: str) -> int: """ 栈 + 动态规划解法 - 时间复杂度O(n)，空间复杂度O(n) """ max_length = 0 stack = [-1] # 栈底保存最后一个未匹配的右括号位置 for i, char in enumerate(s): if char == '(': stack.append(i) else: stack.pop() if not stack: stack.append(i) # 当前右括号无法匹配 else: max_length = max(max_length, i - stack[-1]) return max_length
📊 复杂度分析
时间复杂度：O(n) - 只需要遍历一次
空间复杂度：O(n) - 最坏情况下栈的大小为n
🌟 算法精髓
这个算法的巧妙之处在于"位置记录"。我们不直接记录括号，而是记录它们的位置，通过位置差来计算有效长度，同时用栈底元素作为分界点。
🎯 小白友好贴士
stack = [-1] 初始化栈，-1作为虚拟边界
if char == '(' 左括号入栈
stack.pop() 右括号出栈
if not stack 栈为空说明无法匹配
stack.append(i) 无法匹配的右括号作为新边界
max_length = max(max_length, i - stack[-1]) 计算有效长度
🔍 算法执行过程示例
示例：s = ")()())"初始：max_length = 0, stack = [-1]第1步：i = 0, char = ')' stack.pop() → stack = [] 栈为空，无法匹配，stack.append(0) stack = [0] max_length = 0第2步：i = 1, char = '(' 左括号入栈 stack = [0, 1] max_length = 0第3步：i = 2, char = ')' stack.pop() → stack = [0] 栈不为空，计算长度：2 - 0 = 2 max_length = max(0, 2) = 2 stack = [0]第4步：i = 3, char = '(' 左括号入栈 stack = [0, 3] max_length = 2第5步：i = 4, char = ')' stack.pop() → stack = [0] 栈不为空，计算长度：4 - 0 = 4 max_length = max(2, 4) = 4 stack = [0]第6步：i = 5, char = ')' stack.pop() → stack = [] 栈为空，无法匹配，stack.append(5) stack = [5] max_length = 4结束：return max_length = 4 ✅验证：最长有效括号为 "()()"，长度为4
🎯 核心思想总结
位置记录：用栈记录括号位置而非括号本身
边界管理：栈底元素作为分界点
长度计算：通过位置差计算有效长度
动态更新：实时维护最大长度
