QR 面试最爱
🔖 #70 · Climbing Stairs ★
难度: Easy | 标签: DP | 链接: https://leetcode.com/problems/climbing-stairs/
题目描述
每次可以爬 1 或 2 阶，求到达第 n 阶有多少种方法。
解题思路
dp[i] = dp[i-1] + dp[i-2]，即 Fibonacci 数列。答案代码
def climbStairs(n): a, b = 1, 1 for _ in range(2, n+1): a, b = b, a + b return b
扩展总结
- 属于完全背包入门：#322 Coin Change 等价
- 面试常问：如果可以爬 1/2/3 阶怎么计算？
🔖 #322 · Coin Change ★
难度: Medium | 标签: DP, BFS | 链接: https://leetcode.com/problems/coin-change/
题目描述
给定硬币面値和总金额，求凑满该金额所需的最少硬币数量。
解题思路
完全背包：
dp[i] = min(dp[i], dp[i-c] + 1) for each coin c。答案代码
def coinChange(coins, amount): dp = [float('inf')] * (amount + 1) dp[0] = 0 for i in range(1, amount + 1): for c in coins: if i >= c: dp[i] = min(dp[i], dp[i-c] + 1) return dp[amount] if dp[amount] != float('inf') else -1
扩展总结
- 完全背包特征：每种硬币可用无限次
- #518 Coin Change 2：记录方案数而非最少数量
- 也可用 BFS（层层搜索）解决
🔖 #300 · Longest Increasing Subsequence ★
难度: Medium | 标签: DP, Binary Search | 链接: https://leetcode.com/problems/longest-increasing-subsequence/
题目描述
找数组中最长严格递增子序列的长度。
解题思路
- O(n²) DP：
dp[i] = max(dp[j]+1) for j < i and nums[j] < nums[i]
- O(n log n) 二分优化：维护一个
tails数组，用二分查找插入位置。
答案代码
import bisect def lengthOfLIS(nums): tails = [] for n in nums: pos = bisect.bisect_left(tails, n) if pos == len(tails): tails.append(n) else: tails[pos] = n return len(tails)
扩展总结
- O(n log n) 版本在 QR 面试中必须掌握
- 变体：#354 Russian Doll Envelopes — 二维LIS
tails是各长度LIS的尾部最小元素
🔖 #72 · Edit Distance
难度: Medium | 标签: DP, String | 链接: https://leetcode.com/problems/edit-distance/
题目描述
给定两个字符串 word1 和 word2，求将 word1 转换为 word2 所需的最少操作数。
解题思路
二维 DP：
dp[i][j] = word1[:i] 和 word2[:j] 的编辑距离。- 如果
word1[i] == word2[j]：dp[i][j] = dp[i-1][j-1]
- 否则：
dp[i][j] = 1 + min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1])
答案代码
def minDistance(word1, word2): m, n = len(word1), len(word2) dp = list(range(n+1)) for i in range(1, m+1): prev = dp[0] dp[0] = i for j in range(1, n+1): tmp = dp[j] if word1[i-1] == word2[j-1]: dp[j] = prev else: dp[j] = 1 + min(prev, dp[j], dp[j-1]) prev = tmp return dp[n]
扩展总结
- 字符串DP经典题，#1143 LCS 是它的变体
- 空间压缩：只需一个一维数组即可
🔖 #152 · Maximum Product Subarray
难度: Medium | 标签: DP | 链接: https://leetcode.com/problems/maximum-product-subarray/
题目描述
找数组中乘积最大的连续子数组。
解题思路
因为负数存在，同时维护
cur_max 和 cur_min。答案代码
def maxProduct(nums): res = cur_max = cur_min = nums[0] for n in nums[1:]: candidates = (n, cur_max * n, cur_min * n) cur_max, cur_min = max(candidates), min(candidates) res = max(res, cur_max) return res
扩展总结
- 与 #53 Maximum Subarray 对比学习
- 负数 × 负数 = 正数，最小值可能在乘以负数后变为最大值
🔖 #312 · Burst Balloons
难度: Hard | 标签: DP | 链接: https://leetcode.com/problems/burst-balloons/
题目描述
给定
n 个气球，每个气球有一个数字。戳破第 i 个气球可以获得 nums[i-1] * nums[i] * nums[i+1] 的硬币。求戳破所有气球能获得的最大硬币数。解题思路
逆向思维：不想"第一个戳哪个"，而是想"最后一个戳哪个"。
定义
dp[i][j] = 戳破区间 (i, j) 内所有气球能获得的最大硬币数（不含边界 i 和 j）。枚举区间内最后一个被戳破的气球
k，此时 i 和 j 还在，所以收益是 nums[i] * nums[k] * nums[j]。dp[i][j] = max(dp[i][k] + nums[i]*nums[k]*nums[j] + dp[k][j]) 其中 k 遍历 (i, j) 内所有位置
答案代码
def maxCoins(nums): nums = [1] + nums + [1] # 两端加虚拟气球，值为1 n = len(nums) dp = [[0] * n for _ in range(n)] for length in range(2, n): # 区间长度从小到大 for i in range(n - length): j = i + length for k in range(i+1, j): # k 是区间内最后被戳的 dp[i][j] = max(dp[i][j], dp[i][k] + nums[i] * nums[k] * nums[j] + dp[k][j]) return dp[0][n-1]
举例推导
nums = [3, 1, 5, 8] 补全后 = [1, 3, 1, 5, 8, 1] 最优策略：最后戳 3 → 最后戳 5 → 最后戳 1 → 最后戳 8 coins = 1×3×1 + 1×5×8 + 1×1×8 + 1×8×1 → 167
扩展总结
- 逆向思维是关键：正向想"先戳哪个"边界会不断变化难以定义状态；反过来想"最后戳哪个"边界固定，状态清晰
- 区间DP模板：外层枚举区间长度，内层枚举左端点，最内层枚举分割点，与 #1039 Minimum Score Triangulation 同类
- 虚拟边界
[1] + nums + [1]是常见技巧，避免越界判断