动态规划的基础与解题流程
哪些公司问过
答案要点
- 适用条件:重叠子问题 + 最优子结构;保存子问题结果避免重复计算
- 步骤:定义状态 → 状态转移方程 → 初始条件与边界 → 遍历顺序 → 确定答案
- 爬楼梯:dp[i] = dp[i-1] + dp[i-2]
- 实现:自顶向下的记忆化递归;自底向上的表格递推;可用滚动数组优化空间
- 0/1 背包一维 dp 要逆序遍历容量;经典题:背包、LIS、LCS、编辑距离、路径问题
易错点
- 状态定义不清楚,转移方程写不出来
- 忘了初始条件和边界
- 0/1 背包一维数组用正序遍历
- 把贪心问题当作动态规划,或相反
面试官常见追问
- 动态规划和分治、贪心有什么区别?
- 0/1 背包为什么要逆序遍历容量?
- 怎么优化动态规划的空间?
- 如何判断一个问题能不能用动态规划?
完整的口述示范答案、每个追问的参考回答,在启面刷题中心查看;也可以让 AI 面试官用语音按这道题连环追问你。
相关面试题
- 最长递增子序列(LIS)27 场
- 爬楼梯(青蛙跳台阶)18 场
- 不同路径(网格路径数)17 场
- 买卖股票的最佳时机16 场
- 编辑距离的动态规划解法16 场
- 零钱兑换:最少硬币数与组合数12 场
- 最长公共子序列(LeetCode 1143)11 场
- 矩阵最小路径和(动态规划)10 场
- 斐波那契数列的几种解法8 场
- 背包界面优化与背包问题6 场