掌握动态规划，从“什么问题适合用”及“解题思路”入手
💡
原文中文，约4900字，阅读约需12分钟。
📝
内容提要
本文介绍了用动态规划算法解决硬币找零问题，求最少需要多少个硬币。动态规划算法高效，因为回溯算法中存在大量重复子问题。
🎯
关键要点
- 动态规划算法用于解决最优问题，特别是硬币找零问题。
- 动态规划模型被定义为多阶段决策最优解模型。
- 最优子结构：问题的最优解包含子问题的最优解。
- 无后效性：后续状态只依赖于前面阶段的状态，不受后续决策影响。
- 重复子问题：不同决策序列可能产生相同状态。
- 通过具体实例（如矩阵路径问题）来理解动态规划的特征。
- 动态规划解题思路有两种：状态转移表法和状态转移方程法。
- 状态转移表法：通过回溯算法识别重复子问题，构建状态表并填充。
- 状态转移方程法：根据最优子结构写出递归公式并实现。
- 动态规划与回溯算法相比更高效，但并非所有问题都适合动态规划。
- 贪心算法是动态规划的一种特殊情况，解决问题更高效但适用范围有限。
- 适合动态规划的问题需满足三个特征：最优子结构、无后效性和重复子问题。
- 练习题：给定几种硬币，求支付特定金额所需的最少硬币数。
➡️
