Question

动态规划的核心是什么原理的应用?( )

Answer 1

动态规划的核心原理是最优子结构和重叠子问题。

• 最优子结构：动态规划将大问题划分为小问题，并利用最优子结构的性质，即全局最优解可以通过局部最优解来构建。换句话说，如果一个问题的最优解可以由其子问题的最优解推导得出，那么该问题具有最优子结构。

动态规划例子

• 重叠子问题：在动态规划中，问题的求解往往涉及到重复计算相同的子问题。为了避免重复计算，动态规划使用记忆化技术或者建立一个表格（通常是一个二维数组）来存储已经计算过的子问题的解，以便在需要时直接查找，避免重复计算。

拆分子问题

基于最优子结构和重叠子问题的原理，动态规划可以将复杂的问题分解为一系列的子问题，并逐步求解子问题的最优解，最终得到原问题的最优解。通过存储已经计算过的子问题的解，可以避免重复计算，提高算法的效率。

因此，动态规划的核心是通过寻找最优子结构和利用重叠子问题的特点，将复杂的问题简化为可解决的子问题，并通过组合子问题的解来求解原问题的最优解。