C++动态规划学习（227版本）
发布时间
阅读量：
阅读量
1.动态规划
动态规划算法类似于分治法，在基本原理上也存在相似之处：两者都旨在将复杂的问题分解为若干个较为简单的子问题，并通过求解这些子问题来实现对原问题的整体解答。然而，在具体应用上存在显著差异：适合采用动态规划方法求解的问题具有特定特征——其分解出的子问题是高度相关的而非完全独立的。与分治法相比，在处理这些问题时会面临更多的计算量：具体来说，在相同规模下可能需要执行更多的计算操作才能获得最终结果。尽管如此，在某些情况下这种计算量仍然是可接受甚至必要的。为了提高效率并减少冗余计算，在实际应用中常会采用记忆化技术：即在反复调用同一函数时记住已经计算过的结果并直接调用存储的结果以避免重复计算带来的性能损失。
为了实现这一目标，通常会采用一种表格化的方法：通过建立一个数据结构来存储所有已解决过的子问題的答案（无论该答案是否后续会被再次使用）。这种方法能够有效避免重复计算从而显著提升算法效率。
基于上述核心思想的具体动态规划算法实现方式千差万别但它们都遵循相同的构建模式：
(1）明确最优解的关键属性并揭示其内在结构特征
(2）确定状态转移方程
(3）设定边界条件
(4）构建状态转移表
还没有任何评论哟~