动态规划
动态规划是一种通过将复杂问题分解为子问题，存储子问题的解来避免重复计算的算法设计技术。它适用于具有最优子结构和重叠子问题性质的问题。
基本思想
动态规划的基本思想是：将原问题分解为若干个子问题，先求解子问题，并将子问题的解存储起来（通常使用表格或数组），当需要再次求解相同的子问题时，直接从存储中获取结果，避免重复计算。最后通过组合子问题的解，得到原问题的解。
核心要素
- 最优子结构：问题的最优解包含其子问题的最优解
- 重叠子问题：问题可以被分解为重复的子问题
- 边界条件：问题规模最小时可以直接求解
- 状态转移方程：描述子问题之间关系的方程
实现步骤
- 定义状态：确定需要存储哪些子问题的解
- 建立状态转移方程：找出子问题之间的关系
- 确定边界条件：确定最小规模问题的解
- 计算顺序：确定计算子问题的顺序（自底向上或自顶向下）
- 得到原问题的解
两种实现方式
- 自顶向下（记忆化搜索）：使用递归，将子问题的解存储起来
- 自底向上（迭代）：使用循环，从最小规模问题开始逐步求解
时间复杂度
动态规划的时间复杂度通常为 O(n × m)，其中 n 和 m 是问题的规模。具体复杂度取决于问题的状态数量和状态转移的计算量。
空间复杂度
动态规划的空间复杂度通常为 O(n × m)，用于存储子问题的解。可以通过优化（如滚动数组）来降低空间复杂度。
适用场景
- 最优化问题（如最短路径、最大收益等）
- 计数问题（如路径数量、方案数量等）
- 具有重叠子问题和最优子结构的问题
经典问题
- 斐波那契数列
- 背包问题（0/1背包、完全背包等）
- 最长公共子序列
- 最长递增子序列
- 最短路径问题（如Dijkstra算法）
- 数字金字塔问题
优缺点
- 优点：避免重复计算，提高效率；适用于最优化问题；可以处理复杂问题
- 缺点：需要额外的空间存储子问题的解；需要设计状态和状态转移方程；不适用于所有问题