动态规划原理
动态规划（Dynamic Programming, DP）是一种解决最优化问题的算法范式，核心思想是分治递归 + 记忆存储。
核心概念
- 无记忆递归：子问题被独立对待，同一子问题可能被多次求解，导致大量重复计算
- 动态规划：将原始问题划分为有限的子问题，将子问题的解对应到一张表中，对于公共子问题直接查表获取之前的结果，避免重复计算
思考方式
- 自上向下思考：思考如何分解问题，如何更新状态
- 自下向上计算：先计算最小子问题，不断合并更新，直到最终要求的问题
优化解
优化解（Optimal Solution）是指已经达到最小代价或最大价值的方法解。动态规划的目标就是求出整个问题的优化解。
适用条件
- 最优子结构：问题的最优解包含子问题的最优解
- 重叠子问题：子问题在求解过程中重复出现
链接到
- 上一个知识点：无（本章第一个知识点）
- 下一个知识点：2.2 矩阵链乘法