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

__ryp__ · 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}\vert = \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。

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