动态规划基础

动态规划是解决复杂问题的重要范式，其核心思想是将大问题分解为相互关联的子问题。
与暴力递归相比，动态规划通过存储子问题的解来避免重复计算，这种“以空间换时间”的策略大幅提升了效率。成功应用动态规划需要满足两个基本条件：最优子结构和重叠子问题。
最优子结构意味着全局最优解包含局部最优解，而重叠子问题则保证存储的中间结果能够被多次利用。掌握这一思想是进一步学习各类动态规划变体的基础。