动态规划理论基础

文章目录 定义动态规划与分治问题的区别两种方式实现动态规划方法一：带备忘录的自顶向下法方法二：自底向上法 本质核心解题步骤常见题型划分 动态规划方法通常用来求解最优化问题(optimization problem)。这类问题可以有很多可行解，每个解都有一个值，我们希望寻找具有最优值(最小值或最大值)的解。我们称这样的解为问题的一个最优解(an optimal solution)，而不是最优解(the optimal solution)，因为可能有多个解都达到最优值。 分治问题：将问题划分为互不相交的子问题，递归地求解子问题，再将它们的解组合起来，求出原问题的解。 与之相反，动态规划应用于子问题重叠的情况，即不同的子问题具有公共的子子问题(子问题的求解是递归进行的，将其划分为更小的子子问题)。 在这种情况下，分治算法会做许多不必要的工作，它会反复地求解那些公共子子问题。 而动态规划算法对每个子子问题只求解一次，将其解保存在一个表格中，从而无需每次求解一个子子问题时都重新计算，避免了这种不必要的计算工作。 根据是否将子问题的解保存到一个表中，分出两种实现动态规划的方式。 方法一：带备忘录的自顶向下法 此方法仍按自然的递归形式编写过程，但过程会保存每个子问题的解(通常保存在一个数组或散列表中)。当需要一个子问题的解时，过程首先检查是否已经保存过此解。如果是，则直接返回保存的值，从而节省了计算时间，否则，按通常方式计算这个子问题。我们称这个递归过程是带备忘的(memoized),因为它“记住”了之前已经计算出的结果。 方法二：自底向上法 此方法仍按自然的递归形式编写过程，但过程会保存每个子问题的解(通常保存在一个数组或散列表中)。当需要一个子问题的解时，过程首先检查是否已经保存过此解。如果是，则直接返回保存的值，从而节省了计算时间，否则，按通常方式计算这个子问题。我们称这个递归过程是带备忘的(memoized),因为它“记住”了之前已经计算出的结果。 动态规划的本质上是，如何实现对每个子子问题只求解一次，获得最后的结果。 注意状态转移公式（递推公式）是很重要，但动态规划不仅仅只有递推公式。充分理解如何初始化dp数组已经递推公式才是解决动态规划问题的关键。 确定dp数组（dp table）以及下标的含义确定递推公式dp数组如何初始化确定遍历顺序举例推导dp数组 基础入门题背包问题打家劫舍股票问题子序列问题 本篇介绍动态规划的理论基础，后面更加详细就题目本身分析与理论验证。 ps:计划每日更新一篇博客，今日2023-05-11，日更第二十五天。 昨日更新： 花式反转字符串