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