对于线性动态规划，顾名思义指的就是根据题目内容可以得出线性相关的动态规划，如果书有序列（数组）那么状态就是一维的，如果是网格（棋盘）那么就是二维的。前文引例中的题目便是这种类型的。线性动态规划定义状态通常会考虑某类有序事件前面若干子事件的和 接下来我们给出例题 [HNOI2004] 打鼹鼠题目描述 鼹鼠是一种很喜欢挖洞的动物，但每过一定的时间，它还是喜欢把头探出到地面上来透透气的。根据这个特...

动态规划的介绍动态规划(Dynamic Programming)，简称DP，是运筹学的一个分支，用于解决多阶段决策过程中的最优化的一种数学方法，把多阶段问题变换为系列单阶段的问题加以解决的方法。 所以动态规划其实是一种数学方法，是求解某类问题的一种方法，不是一种特定的算法，更没有标准的数学表达式或者明确的定义的一种规则。 动态规划的根本是一种解决问题的思路，思考问题的方式，而不是具体的方法。...

前置知识注意 该算法的前置知识为队列（queue）,如果没有学习，请点击这里进行学习 BFS的介绍BFS（宽度优先搜索 Breadth-First Search）是一种用于图的遍历或搜索的算法。它从一个节点开始，逐层遍历图中的所有节点。BFS通常用队列来实现，因为它需要按照节点的发现顺序来访问它们。 工作原理BFS的工作原理可以总结为以下几个步骤 循环：只要队列不为空，就执行以下操作： 出...

DFS的介绍DFS（深度优先搜索，Depth-First Search）是一种用于遍历或搜索树或图的算法。它从一个节点开始，尽可能深地搜索树的分支，直到到达叶子节点（没有子节点的节点），然后回溯到上一个节点，继续搜索其他分支。这个过程会一直进行，直到所有可能的分支都被探索完毕。 工作原理DFS的工作原理可以总结为以下几个步骤 选择一个起始节点：从树或图的某个节点开始。 探索尽可能深的分支：...