学习高阶差分之前，你需要先学习差分 高阶差分简介 记 $\Delta f(x)=f(x+1)−f(x)$。称 $\Delta f(x)$ 为 $f(x)$ 的一阶差分。 同理：记 $\Delta^n f(x)=\Delta^{n−1}f(x+1)−\Delta^{n−1}f(x)$ 。称 $\Delta^nf(x)$ 为 $f(x)$ 的 $n$ …

动态规划简介 动态规划是理查德·贝尔曼与$1957$年提出的一种方法，他把原问题分解成若干个小问题，自底向上先求解最小的子问题，把结果存储在表格中，求解大的子问题时直接从表格中查询小的子问题的解，以免重复计算，从而提高效率。 动态规划性质 最优子结构 子问题重叠 无后效性 最优子结构是指问题的最优解包括其子问题的最优解。 子问题重叠指的是每次分解出…

在一个图中进行DP，对于部分题目来说随意一个顺序会破坏DP的无后效性原则，例如题目”洛谷：P3387 【模板】缩点“中，需要找出DAG中的一条路径，且这条路径上的点权和最大。我们需要从枚举的第一个点开始，记录$ dp[i] $，表示从第一个点到当前节点的最大点权和，每次向下枚举一个点，都需要保证我们要枚举的这个点的入度为$0$，即保证它不会再被其他…