动态编程实战：FAANG-Coding-Interview-Questions中的12个经典DP问题

动态规划（Dynamic Programming，DP）是FAANG（Facebook、Amazon、Apple、Netflix、Google）等顶级科技公司面试中不可或缺的考点。掌握动态规划不仅能帮助你解决复杂的算法问题，更能培养你高效的问题分析能力。本文将从FAANG-Coding-Interview-Questions项目中精选12个经典动态规划问题，带你系统学习动态规划的核心思想与解题技巧，助你轻松应对面试挑战。

动态规划基础：从入门到精通

动态规划是一种通过将复杂问题分解为重叠子问题，并存储子问题解来避免重复计算的优化技术。其核心思想可以概括为**"记住你已经解决的问题的答案"**。

动态规划的三大要素

1. 状态定义：如何描述子问题
2. 状态转移方程：子问题之间的关系
3. 边界条件：最小子问题的解

动态规划问题通常可以通过两种方式实现：

• 自顶向下：递归+记忆化
• 自底向上：迭代+动态规划数组

12个经典动态规划问题全解析

1. 爬楼梯（Climbing Stairs）

难度：简单
模式：基础DP
出现频率：所有FAANG公司

这是动态规划的入门级问题，其核心是找到状态转移方程。假设你正在爬楼梯，需要n阶才能到达楼顶。每次你可以爬1或2个台阶，有多少种不同的方法可以爬到楼顶？

解题思路：

• 状态定义：dp[i]表示爬到第i阶的方法数
• 状态转移：dp[i] = dp[i-1] + dp[i-2]
• 边界条件：dp[0] = 1, dp[1] = 1

2. 打家劫舍（House Robber）

难度：中等
模式：线性DP
出现频率：所有FAANG公司

你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。

解题思路：

• 状态定义：dp[i]表示前i间房屋能偷窃到的最大金额
• 状态转移：dp[i] = max(dp[i-1], dp[i-2] + nums[i])
• 边界条件：dp[0] = 0, dp[1] = nums[0]

3. 最长递增子序列（Longest Increasing Subsequence）

难度：中等
模式：LIS
出现频率：所有FAANG公司

给定一个无序的整数数组，找到其中最长上升子序列的长度。

解题思路：

• 状态定义：dp[i]表示以nums[i]结尾的最长递增子序列长度
• 状态转移：dp[i] = max(dp[j] + 1) for j < i and nums[j] < nums[i]
• 边界条件：dp[i] = 1 for all i

4. 零钱兑换（Coin Change）

难度：中等
模式：完全背包
出现频率：所有FAANG公司

给定不同面额的硬币 coins 和一个总金额 amount。编写一个函数来计算可以凑成总金额所需的最少的硬币个数。如果没有任何一种硬币组合能组成总金额，返回 -1。

解题思路：

• 状态定义：dp[i]表示凑成金额i所需的最少硬币数
• 状态转移：dp[i] = min(dp[i - coin] + 1) for coin in coins if i >= coin
• 边界条件：dp[0] = 0, dp[i] = amount + 1 (初始化为一个较大值)

5. 最长公共子序列（Longest Common Subsequence）

难度：中等
模式：2D DP
出现频率：所有FAANG公司

给定两个字符串 text1 和 text2，返回这两个字符串的最长公共子序列的长度。

解题思路：

• 状态定义：dp[i][j]表示text1前i个字符和text2前j个字符的最长公共子序列长度
• 状态转移：if text1[i-1] == text2[j-1], then dp[i][j] = dp[i-1][j-1] + 1 else dp[i][j] = max(dp[i-1][j], dp[i][j-1])
• 边界条件：dp[0][j] = 0, dp[i][0] = 0

6. 单词拆分（Word Break）

难度：中等
模式：字符串DP
出现频率：所有FAANG公司

给定一个非空字符串 s 和一个包含非空单词的列表 wordDict，判定 s 是否可以被空格拆分为一个或多个在字典中出现的单词。

解题思路：

• 状态定义：dp[i]表示字符串s的前i个字符是否可以被拆分
• 状态转移：dp[i] = dp[j] && (s[j..i) in wordDict) for j from 0 to i-1
• 边界条件：dp[0] = true

7. 不同路径（Unique Paths）

难度：中等
模式：网格DP
出现频率：所有FAANG公司

一个机器人位于一个 m x n 网格的左上角。机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角。问总共有多少条不同的路径？

解题思路：

• 状态定义：dp[i][j]表示到达(i,j)的不同路径数
• 状态转移：dp[i][j] = dp[i-1][j] + dp[i][j-1]
• 边界条件：dp[0][j] = 1, dp[i][0] = 1

8. 最大子数组和（Maximum Subarray）

难度：中等
模式：Kadane's算法
出现频率：所有FAANG公司

给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。

解题思路：

• 状态定义：dp[i]表示以nums[i]结尾的最大子数组和
• 状态转移：dp[i] = max(nums[i], dp[i-1] + nums[i])
• 边界条件：dp[0] = nums[0]

9. 打家劫舍 II（House Robber II）

难度：中等
模式：环形DP
出现频率：所有FAANG公司

你是一个专业的小偷，计划偷窃沿街的房屋，每间房内都藏有一定的现金。这个地方所有的房屋都围成一圈，这意味着第一个房屋和最后一个房屋是紧挨着的。同时，相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。

解题思路： 这是打家劫舍问题的变种，关键在于处理环形结构。可以将问题分解为两个子问题：

1. 不偷第一间房屋，考虑从第2间到最后1间
2. 不偷最后一间房屋，考虑从第1间到倒数第2间 最终结果为两个子问题的最大值。

10. 解码方法（Decode Ways）

难度：中等
模式：字符串DP
出现频率：所有FAANG公司

一条包含字母 A-Z 的消息通过以下方式进行了编码：'A' -> 1, 'B' -> 2, ..., 'Z' -> 26。给定一个只包含数字的非空字符串，请计算解码方法的总数。

解题思路：

• 状态定义：dp[i]表示前i个字符的解码方法数
• 状态转移：
  • 如果s[i-1] != '0'，dp[i] += dp[i-1]
  • 如果s[i-2:i]在10到26之间，dp[i] += dp[i-2]
• 边界条件：dp[0] = 1, dp[1] = 1 if s[0] != '0' else 0

11. 乘积最大子数组（Maximum Product Subarray）

难度：中等
模式：DP变种
出现频率：所有FAANG公司

给你一个整数数组 nums ，请你找出数组中乘积最大的连续子数组（该子数组中至少包含一个数字），并返回该子数组所对应的乘积。

解题思路： 由于负数的存在，需要同时跟踪最大乘积和最小乘积：

• 状态定义：max_dp[i]表示以nums[i]结尾的最大乘积，min_dp[i]表示以nums[i]结尾的最小乘积
• 状态转移： max_dp[i] = max(nums[i], max_dp[i-1] * nums[i], min_dp[i-1] * nums[i]) min_dp[i] = min(nums[i], max_dp[i-1] * nums[i], min_dp[i-1] * nums[i])
• 边界条件：max_dp[0] = min_dp[0] = nums[0]

12. 最小路径和（Minimum Path Sum）

难度：中等
模式：网格DP
出现频率：所有FAANG公司

给定一个包含非负整数的 m x n 网格 grid ，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。说明：每次只能向下或者向右移动一步。

解题思路：

• 状态定义：dp[i][j]表示到达(i,j)的最小路径和
• 状态转移：dp[i][j] = grid[i][j] + min(dp[i-1][j], dp[i][j-1])
• 边界条件： dp[0][j] = dp[0][j-1] + grid[0][j] dp[i][0] = dp[i-1][0] + grid[i][0]

动态规划学习资源推荐

想要深入学习动态规划，可以参考项目中的以下资源：

• NeetCode-150.md: 包含12道1-D动态规划和11道2-D动态规划问题，系统覆盖各类DP模式
• Blind-75.md: 提供9道精选动态规划问题，均为FAANG面试高频题

掌握动态规划的最佳策略

1. 从基础开始：先掌握1D DP，再挑战2D DP和复杂状态定义
2. 理解而非记忆：重点理解状态定义和转移方程的推导过程
3. 多做练习：通过项目中的NeetCode-150.md和Blind-75.md进行系统训练
4. 总结模式：将问题按类型分类，总结各类问题的通用解法
5. 空间优化：学习如何通过滚动数组等技巧优化DP空间复杂度

动态规划是算法面试的重中之重，也是区分优秀程序员的重要标志。通过系统学习FAANG-Coding-Interview-Questions项目中的经典问题，你将能够建立起完善的动态规划思维体系，轻松应对各类复杂问题。记住，动态规划的核心在于找到正确的状态定义和状态转移方程，而这需要通过大量练习来培养直觉。

祝你的FAANG面试之旅一切顺利！🚀