动态规划是编程面试中最具挑战性且最常考的主题之一。面试官想看你能否识别重叠子问题、定义递推关系，并用记忆化或制表法实现高效解法。
定义DP：一种针对有重叠子问题和最优子结构问题的优化技术。
解释两种方法：自顶向下（记忆化+递归）和自底向上（制表法+迭代）。
用经典例题（如斐波那契或爬楼梯）演示两种方法。
讨论如何识别DP题：计数方案数、求最值、每步做决策。
动态规划通过将问题拆分为重叠子问题并存储结果来避免重复计算。两种方法：自顶向下记忆化，在递归基础上加缓存；自底向上制表法，从最小子问题迭代填表。以爬楼梯为例：每次可以爬1或2阶，到第n阶有多少种方法？递推式是 dp[i] = dp[i-1] + dp[i-2]，dp[0]=1，dp[1]=1。朴素递归 O(2^n)，DP优化后 O(n) 时间。制表法中只需保留前两个值，空间可优化到 O(1)。识别DP题的信号：问计数、最值或最优；每步有选择；解决子问题有助于解决原问题。经典DP题包括背包问题、最长公共子序列和编辑距离。
先写递归暴力解，再加记忆化——这是最简单的DP入门路径。
总是找机会优化空间复杂度，只保留需要的前几个状态。
练习15种经典DP模式（背包、LCS、LIS、矩阵链乘等）——大多数题目都是变体。
记忆化是自顶向下，递归加缓存。制表法是自底向上，从基准情况迭代填表。两者时间复杂度相同。
看是否有重叠子问题（相同子计算重复出现）和最优子结构（最优解由子问题最优解组成）。
不一定。贪心在适用时更快（某些问题 O(n) vs O(n²)），但只有局部最优能导出全局最优时贪心才有效。DP更通用。