（合集）简单动态规划之思路分析最优子结构证明与归纳

本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2023-12-15 22:56:39

我承认我的动态规划真的非常烂，所以我决心要恶补一下。

Ad maiora!

贪心。下面证明。

问题是求在 $T$ 秒内能走的最长距离。有几种选择：

我们要证明的是本问题的最优子结构。如果我们已经有了走到 $t - 1$ 时间的最优解 $P_{1, t - 1}$，要证走到 $T$ 时间的最优解一定包含 $P_{1, t - 1}$ 。

用标准的 cut-and-paste。设 $Q_{1, t}$ 才是到 $t$ 时间的最优解，那么一定有 $Q_{1, t - 1} \gt P_{1, t - 1}$。

如果 $Q_T$ 是操作 A，那么 $\lvert Q_{1,t}\ert = \lvert P_{1,t-1}\rvert$。矛盾，得证。
如果 $Q_T$ 是操作 B，那么明显将 $P_{t-1}$ 嫁接到 $Q$ 上对其没有任何影响，况且可以得到 $\lvert Q_T\rvert \gt \lvert Q_{1, t} - Q_{1, t-1} + P_{1, t-1}\rvert$。矛盾，得证。
如果 $Q_T$ 是操作 C，那么我们知道 $M_Q(t-1) \ge 10$。我们要证 $M_P(t-1) \ge 10$。

（情况 1）： 如果正如此，那么没有什么好证明的。
（情况 2）： 如果并非如此，即 $M_P(t-1) < 10$，这就意味着 $P_{1,t-1}$ 一定比 $Q$ 多至少一次操作 C，$Q_{1,t-1}$ 一定比 $P$ 多至少一次操作 A，因此 $\lvert P_{1,t-1}\rvert - \lvert Q_{1,t}\rvert \ge 60$。于是，$\lvert Q_{1,t}\rvert + 60 \le \lvert P_{1,t-1}\rvert$，更有 $\lvert Q_{1,t}\rvert + 60 \lt \lvert P_{1,t-1}\rvert + 17$。这也就是说 $Q_{1,t}$ 甚至比不上 $P_{1,t-1}$。这显然是矛盾的，得证。

于是得证。

归纳边界：当 $t = 0$ 时明显最大距离为 0。

设 $t$ 对于本问题是前 $t$ 秒的最优解，那么对于前 $t + 1$ 秒，由于最优子结构性质，我们只需要考虑在操作 A、B 与 C 中进行选择，选择最大者即可。

最优子结构易证。

我们设 $f(i)$ 表示从 $1$ 到 $i$ 的最小租金。归纳边界是 $f(1) = 0$。

要走到第 $i$ 个回收站，我们可以从 $1, \cdots, i - 1$ 的回收站里选一个进行租用。那么方程就是

$$ f(i) = \begin{cases} 0 & i = 1 \ \min\limits_{1\le j\lt i} f(j) + r(j, i) & \text{otherwise} \end{cases} $$

计数 DP。要求的是方案数量。设 $f(i, j)$ 是在这个集合的前 $i$ 个元素中表示 $j$ 的方案数。

归纳边界明显：$f(i, 0) = 1$。

一般地，要表示 $j$，只有两种方法：$j$ (1) 和 $(j - p_i) + p_i$。那么，表示出 $j$ 的方案数，就是原来的方案数量加上 $f(i - 1, j - p_i)$

但是最终的答案要减去每一个 (1)。即，最终的答案要减去 $m$。

ryp 的博客