算法面试题：动态规划

1. 动态规划的核心思想是什么？

• 将原问题拆分为子问题。
• 通过保存子问题结果避免重复计算。
• 适合具有重叠子问题和最优子结构的问题。

2. 递归、记忆化和 DP 表三者关系是什么？

• 递归描述问题规模缩减。
• 记忆化在递归上缓存结果。
• DP 表通过迭代方式逐步填表。

3. 如何设计状态与状态转移？

• 确定状态表示问题的关键变量。
• 定义状态转移方程描述子问题与当前问题关系。

4. 经典动态规划题有哪些？

• 斐波那契数列。
• 背包问题。
• 最长公共子序列。
• 最长递增子序列。

5. 时间复杂度和空间优化如何做？

• 根据状态个数估算时间复杂度。
• 使用滚动数组或状态压缩降低空间。

6. 何时使用动态规划？

• 问题有重叠子问题。
• 需要最优解而非贪心解。
• 可以通过子问题构造全局解。

7. 动态规划与贪心算法的区别？

• 贪心每步选最优局部解，不一定得到全局最优。
• 动态规划考虑所有子问题，适用于全局最优问题。

8. 动态规划面试中常见问法有哪些？

• 解释状态转移方程。
• 说明如何初始化边界条件。
• 描述如何从 DP 表中恢复答案。