62.不同路径
🎭 题目小剧场
想象你在一个迷宫的左上角，要走到右下角。你只能向右或向下移动，就像在棋盘上走格子，每一步都要做出选择。你需要计算出有多少种不同的走法！
💡 解题思路
动态规划解法：
确定状态：dpi 表示到达位置(i,j)的不同路径数
状态转移：dpi = dpi-1 + dpi（从上方或左方到达）
初始条件：第一行和第一列都为1（只有一种走法）
逐步计算整个网格
🐍 Python代码实现
class Solution: def uniquePaths(self, m: int, n: int) -> int: """ 动态规划解法 - 时间复杂度O(m×n)，空间复杂度O(n) """ # 使用一维数组优化空间 dp = [1] * n for i in range(1, m): for j in range(1, n): dp[j] = dp[j] + dp[j-1] return dp[-1]
📊 复杂度分析
时间复杂度：O(m×n) - 需要遍历整个网格
空间复杂度：O(n) - 使用一维数组优化空间
🌟 算法精髓
这个算法的巧妙之处在于"空间优化"。我们不需要存储整个二维数组，只需要一行即可，因为当前行的计算只依赖于当前行和上一行的数据。
🎯 小白友好贴士
dp = [1] * n 初始化第一行，都为1
for i in range(1, m) 从第二行开始
for j in range(1, n) 从第二列开始
dp[j] = dp[j] + dp[j-1] 状态转移方程
return dp[-1] 返回右下角的路径数
🔍 算法执行过程示例
示例：m = 3, n = 7初始：dp = [1, 1, 1, 1, 1, 1, 1]第1行（i = 0）：保持不变 dp = [1, 1, 1, 1, 1, 1, 1]第2行（i = 1）： j = 1: dp[1] = dp[1] + dp[0] = 1 + 1 = 2 j = 2: dp[2] = dp[2] + dp[1] = 1 + 2 = 3 j = 3: dp[3] = dp[3] + dp[2] = 1 + 3 = 4 j = 4: dp[4] = dp[4] + dp[3] = 1 + 4 = 5 j = 5: dp[5] = dp[5] + dp[4] = 1 + 5 = 6 j = 6: dp[6] = dp[6] + dp[5] = 1 + 6 = 7 dp = [1, 2, 3, 4, 5, 6, 7]第3行（i = 2）： j = 1: dp[1] = dp[1] + dp[0] = 2 + 1 = 3 j = 2: dp[2] = dp[2] + dp[1] = 3 + 3 = 6 j = 3: dp[3] = dp[3] + dp[2] = 4 + 6 = 10 j = 4: dp[4] = dp[4] + dp[3] = 5 + 10 = 15 j = 5: dp[5] = dp[5] + dp[4] = 6 + 15 = 21 j = 6: dp[6] = dp[6] + dp[5] = 7 + 21 = 28 dp = [1, 3, 6, 10, 15, 21, 28]结束：return dp[-1] = 28 ✅
🎯 核心思想总结
状态定义：明确dp数组的含义
状态转移：找到递推关系
初始条件：确定边界值
空间优化：减少不必要的存储
64.最小路径和
🎭 题目小剧场
想象你在一个数字迷宫的左上角，每走一步都要付出相应的"代价"。你要找到一条从左上角到右下角的路径，使得总代价最小。就像在棋盘上收集金币，每格都有不同数量的金币，你要规划路线收集最多的金币！
💡 解题思路
动态规划解法：
确定状态：dpi 表示到达位置(i,j)的最小路径和
状态转移：dpi = gridi + min(dpi-1, dpi)
初始条件：dp0 = grid0，第一行和第一列需要特殊处理
逐步计算整个网格
🐍 Python代码实现
class Solution: def minPathSum(self, grid: List[List[int]]) -> int: """ 动态规划解法 - 时间复杂度O(m×n)，空间复杂度O(n) """ if not grid or not grid[0]: return 0 m, n = len(grid), len(grid[0]) dp = [0] * n for i in range(m): for j in range(n): if i == 0 and j == 0: dp[j] = grid[i][j] elif i == 0: dp[j] = dp[j-1] + grid[i][j] elif j == 0: dp[j] = dp[j] + grid[i][j] else: dp[j] = min(dp[j], dp[j-1]) + grid[i][j] return dp[-1]
📊 复杂度分析
时间复杂度：O(m×n) - 需要遍历整个网格
空间复杂度：O(n) - 使用一维数组优化空间
🌟 算法精髓
这个算法的巧妙之处在于"原地更新"。我们直接在输入网格上进行修改，或者使用一维数组，避免了额外的空间开销，同时保证了计算的正确性。
🎯 小白友好贴士
if not grid or not grid[0] 处理空网格
dp = [0] * n 初始化一维数组
if i == 0 and j == 0 处理起始点
elif i == 0 处理第一行
elif j == 0 处理第一列
dp[j] = min(dp[j], dp[j-1]) + grid[i][j] 状态转移方程
🔍 �算法执行过程示例
示例：grid = [ [1, 3, 1], [1, 5, 1], [4, 2, 1]]初始：dp = [0, 0, 0]第1行（i = 0）： j = 0: dp[0] = grid[0][0] = 1 j = 1: dp[1] = dp[0] + grid[0][1] = 1 + 3 = 4 j = 2: dp[2] = dp[1] + grid[0][2] = 4 + 1 = 5 dp = [1, 4, 5]第2行（i = 1）： j = 0: dp[0] = dp[0] + grid[1][0] = 1 + 1 = 2 j = 1: dp[1] = min(dp[1], dp[0]) + grid[1][1] = min(4, 2) + 5 = 7 j = 2: dp[2] = min(dp[2], dp[1]) + grid[1][2] = min(5, 7) + 1 = 6 dp = [2, 7, 6]第3行（i = 2）： j = 0: dp[0] = dp[0] + grid[2][0] = 2 + 4 = 6 j = 1: dp[1] = min(dp[1], dp[0]) + grid[2][1] = min(7, 6) + 2 = 8 j = 2: dp[2] = min(dp[2], dp[1]) + grid[2][2] = min(6, 8) + 1 = 7 dp = [6, 8, 7]结束：return dp[-1] = 7 ✅验证：最小路径为 1→3→1→1→1，和为7
🎯 核心思想总结
状态定义：明确dp数组的含义
状态转移：找到递推关系
边界处理：特殊处理第一行和第一列
空间优化：使用一维数组减少空间
5.最长回文子串
🎭 题目小剧场
想象你在玩一个找对称的游戏，给定一串字符，你要找出最长的对称片段。就像照镜子，左边的字符和右边的字符要完全一样，比如 "aba" 或 "abba"。
💡 解题思路
中心扩展法：
每个字符（或字符间隙）都可以作为回文中心
从中心向两边扩展，检查是否构成回文
处理两种情况：奇数长度（单字符中心）和偶数长度（字符间隙中心）
维护最长回文子串的起始位置和长度
🐍 Python代码实现
class Solution: def longestPalindrome(self, s: str) -> str: """ 中心扩展法 - 时间复杂度O(n²)，空间复杂度O(1) """ if not s: return "" start = 0 max_length = 1 for i in range(len(s)): # 奇数长度回文（中心为单个字符） self.expandAroundCenter(s, i, i, start, max_length) # 偶数长度回文（中心为字符间隙） self.expandAroundCenter(s, i, i + 1, start, max_length) return s[start:start + max_length] def expandAroundCenter(self, s: str, left: int, right: int, start: int, max_length: int): while left >= 0 and right < len(s) and s[left] == s[right]: current_length = right - left + 1 if current_length > max_length: max_length = current_length start = left left -= 1 right += 1 return start, max_length
📊 复杂度分析
🌟 算法精髓
这个算法的巧妙之处在于"中心思想"。我们不直接枚举所有子串，而是枚举所有可能的中心，然后从中心向两边扩展，大大减少了计算量。
🎯 小白友好贴士
if not s: return "" 处理空字符串
start = 0, max_length = 1 初始化结果
for i in range(len(s)) 遍历所有可能中心
expandAroundCenter(s, i, i) 处理奇数长度
expandAroundCenter(s, i, i + 1) 处理偶数长度
while left >= 0 and right < len(s) and s[left] == s[right] 扩展条件
🔍 算法执行过程示例
示例：s = "babad"初始：start = 0, max_length = 1第1步：i = 0 奇数中心 (0, 0): left = 0, right = 0, s[0] = 'b' = s[0] = 'b' current_length = 1, max_length = 1, start = 0 left = -1, right = 1, 停止 偶数中心 (0, 1): left = 0, right = 1, s[0] = 'b' ≠ s[1] = 'a' 停止第2步：i = 1 奇数中心 (1, 1): left = 1, right = 1, s[1] = 'a' = s[1] = 'a' current_length = 1, max_length = 1, start = 0 left = 0, right = 2, s[0] = 'b' ≠ s[2] = 'b' 停止 偶数中心 (1, 2): left = 1, right = 2, s[1] = 'a' ≠ s[2] = 'b' 停止第3步：i = 2 奇数中心 (2, 2): left = 2, right = 2, s[2] = 'b' = s[2] = 'b' current_length = 1, max_length = 1, start = 0 left = 1, right = 3, s[1] = 'a' = s[3] = 'a' current_length = 3, max_length = 3, start = 1 left = 0, right = 4, s[0] = 'b' ≠ s[4] = 'd' 停止 偶数中心 (2, 3): left = 2, right = 3, s[2] = 'b' ≠ s[3] = 'a' 停止第4步：i = 3 奇数中心 (3, 3): left = 3, right = 3, s[3] = 'a' = s[3] = 'a' current_length = 1, max_length = 3, start = 1 left = 2, right = 4, s[2] = 'b' ≠ s[4] = 'd' 停止 偶数中心 (3, 4): left = 3, right = 4, s[3] = 'a' ≠ s[4] = 'd' 停止第5步：i = 4 奇数中心 (4, 4): left = 4, right = 4, s[4] = 'd' = s[4] = 'd' current_length = 1, max_length = 3, start = 1left = 3, right = 5, 停止偶数中心 (4, 5):left = 4, right = 5, 停止结束：return s[1:1+3] = "bab" ✅验证：最长回文子串为 "bab" 或 "aba"，长度为3
🎯 核心思想总结
中心思想：每个字符和间隙都可以作为中心
双向扩展：从中心向两边同时扩展
奇偶处理：分别处理奇数和偶数长度的回文
实时更新：发现更长回文时立即更新结果
1143.最长公共子序列
🎭 题目小剧场
想象你有两串字符，像两条不同的项链。你要找出这两条项链上最长的相同字符序列，这些字符可以不连续，但必须保持原有的相对顺序。就像在两本书中找出最长的相同句子片段！
💡 解题思路
动态规划解法：
确定状态：dpi 表示text1的前i个字符和text2的前j个字符的最长公共子序列长度
状态转移：
(1) 如果text1[i-1] == text2[j-1]：dpi = dpi-1 + 1
(2) 如果text1[i-1] != text2[j-1]：dpi = max(dpi-1, dpi)
初始条件：dp0 = dpi = 0（空字符串的LCS为0）
逐步计算整个二维数组
🐍 Python代码实现
class Solution: def longestCommonSubsequence(self, text1: str, text2: str) -> int: """ 动态规划解法 - 时间复杂度O(m×n)，空间复杂度O(n) """ m, n = len(text1), len(text2) # 使用一维数组优化空间 dp = [0] * (n + 1) for i in range(1, m + 1): prev = 0 # 保存dp[i-1][j-1]的值 for j in range(1, n + 1): temp = dp[j] # 保存当前的dp[i-1][j] if text1[i-1] == text2[j-1]: dp[j] = prev + 1 else: dp[j] = max(dp[j], dp[j-1]) prev = temp return dp[n]
📊 复杂度分析
🌟 算法精髓
这个算法的巧妙之处在于"空间优化"。我们观察到当前状态只依赖于左上方、上方和左方的状态，因此可以用一维数组加上一个临时变量来存储必要信息。
🎯 小白友好贴士
m, n = len(text1), len(text2) 获取字符串长度
dp = [0] * (n + 1) 初始化一维数组
prev = 0 保存左上角的值
temp = dp[j] 保存当前格子上方的值
if text1[i-1] == text2[j-1] 字符匹配的情况
dp[j] = prev + 1 匹配时长度加1
dp[j] = max(dp[j], dp[j-1]) 不匹配时取较大值
🔍 算法执行过程示例
示例：text1 = "abcde", text2 = "ace"初始：m = 5, n = 3, dp = [0, 0, 0, 0]第1行（i = 1, text1[0] = 'a'）：prev = 0j = 1: text1[0] = 'a' == text2[0] = 'a'temp = dp[1] = 0dp[1] = prev + 1 = 1prev = temp = 0j = 2: text1[0] = 'a' != text2[1] = 'c'temp = dp[2] = 0dp[2] = max(dp[2], dp[1]) = max(0, 1) = 1prev = temp = 0j = 3: text1[0] = 'a' != text2[2] = 'e'temp = dp[3] = 0dp[3] = max(dp[3], dp[2]) = max(0, 1) = 1prev = temp = 0dp = [0, 1, 1, 1]第2行（i = 2, text1[1] = 'b'）：prev = 0j = 1: text1[1] = 'b' != text2[0] = 'a'temp = dp[1] = 1dp[1] = max(dp[1], dp[0]) = max(1, 0) = 1prev = temp = 1j = 2: text1[1] = 'b' != text2[1] = 'c'temp = dp[2] = 1dp[2] = max(dp[2], dp[1]) = max(1, 1) = 1prev = temp = 1j = 3: text1[1] = 'b' != text2[2] = 'e'temp = dp[3] = 1dp[3] = max(dp[3], dp[2]) = max(1, 1) = 1prev = temp = 1dp = [0, 1, 1, 1]第3行（i = 3, text1[2] = 'c'）：prev = 0j = 1: text1[2] = 'c' != text2[0] = 'a'temp = dp[1] = 1dp[1] = max(dp[1], dp[0]) = max(1, 0) = 1prev = temp = 1j = 2: text1[2] = 'c' == text2[1] = 'c'temp = dp[2] = 1dp[2] = prev + 1 = 2prev = temp = 1j = 3: text1[2] = 'c' != text2[2] = 'e'temp = dp[3] = 1dp[3] = max(dp[3], dp[2]) = max(1, 2) = 2prev = temp = 1dp = [0, 1, 2, 2]第4行（i = 4, text1[3] = 'd'）：prev = 0j = 1: text1[3] = 'd' != text2[0] = 'a'temp = dp[1] = 1dp[1] = max(dp[1], dp[0]) = max(1, 0) = 1prev = temp = 1j = 2: text1[3] = 'd' != text2[1] = 'c'temp = dp[2] = 2dp[2] = max(dp[2], dp[1]) = max(2, 1) = 2prev = temp = 2j = 3: text1[3] = 'd' != text2[2] = 'e'temp = dp[3] = 2dp[3] = max(dp[3], dp[2]) = max(2, 2) = 2prev = temp = 2dp = [0, 1, 2, 2]第5行（i = 5, text1[4] = 'e'）：prev = 0j = 1: text1[4] = 'e' != text2[0] = 'a'temp = dp[1] = 1dp[1] = max(dp[1], dp[0]) = max(1, 0) = 1prev = temp = 1j = 2: text1[4] = 'e' != text2[1] = 'c'temp = dp[2] = 2dp[2] = max(dp[2], dp[1]) = max(2, 1) = 2prev = temp = 2j = 3: text1[4] = 'e' == text2[2] = 'e'temp = dp[3] = 2dp[3] = prev + 1 = 3prev = temp = 2dp = [0, 1, 2, 3]结束：return dp[3] = 3 ✅验证：最长公共子序列为 "ace"，长度为3
🎯 核心思想总结
状态定义：明确dp数组的含义
状态转移：找到递推关系
空间优化：使用一维数组减少空间
边界处理：正确处理空字符串情况
72.编辑距离
🎭 题目小剧场
想象你是一位文字编辑师，要把单词 "word" 变成 "word1"。你有三种操作：插入一个字符、删除一个字符、替换一个字符。每次操作都算一步，你的目标是找到最少的操作步骤。
💡 解题思路
动态规划解法：
确定状态：dpi 表示word1的前i个字符转换成word2的前j个字符所需的最少操作数
状态转移：
(1) 如果word1[i-1] == word2[j-1]：dpi = dpi-1（无需操作）
(2) 如果word1[i-1] != word2[j-1]：dpi = min(dpi-1 + 1, dpi + 1, dpi-1 + 1)
初始条件：dp0 = j（插入j个字符），dpi = i（删除i个字符）
逐步计算整个二维数组
🐍 Python代码实现
class Solution: def minDistance(self, word1: str, word2: str) -> int: """ 动态规划解法 - 时间复杂度O(m×n)，空间复杂度O(m×n) """ m, n = len(word1), len(word2) # 创建dp数组 dp = [[0] * (n + 1) for _ in range(m + 1)] # 初始化边界条件 for i in range(m + 1): dp[i][0] = i # 删除i个字符 for j in range(n + 1): dp[0][j] = j # 插入j个字符 # 填充dp数组 for i in range(1, m + 1): for j in range(1, n + 1): if word1[i-1] == word2[j-1]: dp[i][j] = dp[i-1][j-1] else: dp[i][j] = min( dp[i-1][j] + 1, # 删除 dp[i][j-1] + 1, # 插入 dp[i-1][j-1] + 1 # 替换 ) return dp[m][n]
📊 复杂度分析
🌟 算法精髓
这个算法的巧妙之处在于"状态定义"。通过定义清晰的子问题，将复杂的字符串转换问题分解为简单的字符比较问题，从而找到最优解。
🎯 小白友好贴士
m, n = len(word1), len(word2) 获取单词长度
dp = [[0] * (n + 1) for _ in range(m + 1)] 创建dp数组
dp[i][0] = i 删除i个字符
dp[0][j] = j 插入j个字符
if word1[i-1] == word2[j-1] 字符匹配的情况
dp[i][j] = dp[i-1][j-1] 匹配时无需操作
dp[i][j] = min(...) 不匹配时取最小操作数
🔍 算法执行过程示例
示例：word1 = "horse", word2 = "ros"初始：m = 5, n = 3dp = [ [0, 1, 2, 3], [1, 0, 0, 0], [2, 0, 0, 0], [3, 0, 0, 0], [4, 0, 0, 0], [5, 0, 0, 0]]第1行（i = 1, word1[0] = 'h'）： j = 1: word1[0] = 'h' != word2[0] = 'r' dp[1][1] = min(dp[0][1] + 1, dp[1][0] + 1, dp[0][0] + 1) = min(1 + 1, 1 + 1, 0 + 1) = 1 j = 2: word1[0] = 'h' != word2[1] = 'o' dp[1][2] = min(dp[0][2] + 1, dp[1][1] + 1, dp[0][1] + 1) = min(2 + 1, 1 + 1, 1 + 1) = 2 j = 3: word1[0] = 'h' != word2[2] = 's' dp[1][3] = min(dp[0][3] + 1, dp[1][2] + 1, dp[0][2] + 1) = min(3 + 1, 2 + 1, 2 + 1) = 3第2行（i = 2, word1[1] = 'o'）： j = 1: word1[1] = 'o' != word2[0] = 'r' dp[2][1] = min(dp[1][1] + 1, dp[2][0] + 1, dp[1][0] + 1) = min(1 + 1, 2 + 1, 1 + 1) = 2 j = 2: word1[1] = 'o' == word2[1] = 'o' dp[2][2] = dp[1][1] = 1 j = 3: word1[1] = 'o' != word2[2] = 's' dp[2][3] = min(dp[1][3] + 1, dp[2][2] + 1, dp[1][2] + 1) = min(3 + 1, 1 + 1, 2 + 1) = 2第3行（i = 3, word1[2] = 'r'）： j = 1: word1[2] = 'r' == word2[0] = 'r' dp[3][1] = dp[2][0] = 2 j = 2: word1[2] = 'r' != word2[1] = 'o' dp[3][2] = min(dp[2][2] + 1, dp[3][1] + 1, dp[2][1] + 1) = min(1 + 1, 2 + 1, 2 + 1) = 2 j = 3: word1[2] = 'r' != word2[2] = 's' dp[3][3] = min(dp[2][3] + 1, dp[3][2] + 1, dp[2][2] + 1) = min(2 + 1, 2 + 1, 1 + 1) = 2第4行（i = 4, word1[3] = 's'）： j = 1: word1[3] = 's' != word2[0] = 'r' dp[4][1] = min(dp[3][1] + 1, dp[4][0] + 1, dp[3][0] + 1) = min(2 + 1, 4 + 1, 3 + 1) = 3 j = 2: word1[3] = 's' != word2[1] = 'o' dp[4][2] = min(dp[3][2] + 1, dp[4][1] + 1, dp[3][1] + 1) = min(2 + 1, 3 + 1, 2 + 1) = 3 j = 3: word1[3] = 's' == word2[2] = 's' dp[4][3] = dp[3][2] = 2第5行（i = 5, word1[4] = 'e'）： j = 1: word1[4] = 'e' != word2[0] = 'r' dp[5][1] = min(dp[4][1] + 1, dp[5][0] + 1, dp[4][0] + 1) = min(3 + 1, 5 + 1, 4 + 1) = 4 j = 2: word1[4] = 'e' != word2[1] = 'o' dp[5][2] = min(dp[4][2] + 1, dp[5][1] + 1, dp[4][1] + 1) = min(3 + 1, 4 + 1, 3 + 1) = 4 j = 3: word1[4] = 'e' != word2[2] = 's' dp[5][3] = min(dp[4][3] + 1, dp[5][2] + 1, dp[4][2] + 1) = min(2 + 1, 4 + 1, 3 + 1) = 3结束：return dp[5][3] = 3 ✅验证：horse → rse → rose → ros，共3步操作
🎯 核心思想总结
状态定义：明确dp数组的含义
状态转移：考虑插入、删除、替换三种操作
边界条件：处理空字符串的情况
最优选择：选择操作数最少的方案
10个月宝宝每天需要喝多少奶粉？