6.2 动态规划

文档摘要

6.2 动态规划 6.2 动态规划动态规划（Dynamic Programming，DP）是一种解决多阶段决策问题的优化方法。它将问题分解为相互重叠的子问题，并解决一次子问题，然后将结果存储起来，避免重复计算，从而提高效率。 6.2.1 动态规划的核心思想动态规划的核心思想可以概括为以下几点：最优子结构（Optimal Substructure）：问题的最优解包含其子问题的最优解。也就是说，可以通过组合子问题的最优解来得到原问题的最优解。重叠子问题（Overlapping Subproblems）：在解决问题的过程中，会多次遇到相同的子问题。动态规划会存储这些子问题的解，避免重复计算，从而提高效率。