一句话总结
动态规划是算法面试的难点，核心考点：三要素（最优子结构+重叠子问题+状态转移方程）、背包问题（0-1背包逆序 vs 完全背包正序）、子序列（LIS/LCS）、路径问题（网格DP）。解题步骤：定义dp含义→推导转移方程→确定初始条件→举例验证。
动态规划核心思想
动态规划三要素：
1. 最优子结构：大问题的最优解包含小问题的最优解。
2. 重叠子问题：递归过程中会重复计算相同的子问题。
3. 状态转移方程：描述大问题和小问题之间的关系。
解题步骤：
1. 定义dp数组含义
2. 推导状态转移方程
3. 确定初始条件和遍历顺序
4. 举例验证
背包问题
0-1背包：每个物品只能选一次。
dp[i][j] = max(dp[i-1][j], dp[i-1][j-w[i]] + v[i])
空间优化：一维数组逆序遍历。
完全背包：每个物品可以选多次。
dp[i][j] = max(dp[i-1][j], dp[i][j-w[i]] + v[i])
空间优化：一维数组正序遍历。
面试变体：零钱兑换、分割等和子集、目标和。
子序列问题
最长递增子序列（LIS）：
dp[i]表示以nums[i]结尾的LIS长度，dp[i] = max(dp[j] + 1) for j < i and nums[j] < nums[i]。时间O(n²)，贪心+二分优化到O(nlogn)。
最长公共子序列（LCS）：
dp[i][j]表示text1前i个和text2前j个的LCS长度。
若text1[i-1]==text2[j-1]：dp[i][j]=dp[i-1][j-1]+1
否则：dp[i][j]=max(dp[i-1][j], dp[i][j-1])
路径问题
不同路径：从左上角到右下角有多少条路径。
dp[i][j] = dp[i-1][j] + dp[i][j-1]，障碍物位置为0。
最小路径和：dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + grid[i][j]
三角形最小路径和：自底向上dp[i][j] = min(dp[i+1][j], dp[i+1][j+1]) + triangle[i][j]