算法动态规划

难以发现的最优子结构：归纳与猜想 | 合情推理 | 问题转化

字数统计: 3.3k字   |   阅读时长: 12分
, , , , ,

摘要: 分析问题的过程猜出最优子结构

【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】
我的网站：潮汐朝夕的生活实验室
我的公众号：算法题刷刷
我的知乎：潮汐朝夕
我的github：FennelDumplings
我的leetcode：FennelDumplings

此前我们解决过大量的动态规划问题，并且也了解了一些理论，对常见问题也形成了套路。

但是有些问题还是需要一些灵光一闪，才能发现其中的最优子结构，这不是理论和套路能解决的，需要对小数据的情况进行分析后提出正确的猜想，需要一些直觉，有时可能还需要推公式。

这里就要提一下重要的数学思维归纳与猜想了。在我们从小到大学习数学的过程中，注重的是论证推理，也就是告诉你正确结论，你需要把它严谨地推导出来。而合情推理，比如类比、猜想、归纳等等，由于可能存在反例，导出的内容不能作为一个正确的结论，因此一般来讲我们是不重视这一步的。

比如一个定理，它在历史上一般有发现和证明这两步，很多时候这两步都不是同一个人完成的。我们学数学掌握的是证明这一步，这也是对的，证明是我们必须重点掌握的。而发现这一步有时会更引人入胜，”第一个提出这个定理的人是怎么想到的”，往往需要一些启发，而不是凭空想出来，这个启发的过程就需要合情推理，也就是怎么怎么大胆且高效地去猜。

即使在论证推理的内部，我们也经常需要使用合情推理。很多证明题，我们抓耳挠腮半天不会做，去看答案的时候经常见到“令…”，“构造…”等等这些步骤，最后发现所有过程全都会，但就是不知道这里为什么要这么令、这步构造到底是怎么想到的。其实最早提供证明过程的人，这些精妙的构造很多一开始也都是猜的，只是厉害的人猜的命中率要高不少。

因此想成为一个好的数学家，就必须首先是一个好的猜想家。有效地应用合情推理，也就是猜答案，也是一种技能，是技能就可以通过模仿和练习掌握。这方面的参考书不多，这里推荐 Polya 的《数学与猜想：数学中的归纳和类比》以及《数学与猜想：合情推理模式》。

本书讨论了数学里大大小小的发现，力求写出一个发现是如何产生的过程来，获得发现的动机，导致发现的合情推理。这是值得模仿的过程，因此给出了很多练习，对每个练习读者可以自己走一遍观察、类比、归纳、猜想等等的合情推理过程。感兴趣的朋友可以自行下载，以后有时间再跟大家一起阅读这本书。

在算法中我们也经常使用归纳与猜想的技巧，比如算法流程中的一些周期性、对称性的发现；比如一些计数问题，先对数据规模很小的情况手算出答案，然后再找到其中的规律，猜出递推关系；比如一些递归式的求解，先猜答案再证明是一种重要的办法，一般称其为代入法。

本文我们看一个例子，通过对几个 Case 的分析，猜出最优子结构，进而列出动态规划状态转移方程。如果不敢猜，就想不到动态规划的办法。后续的优化状态表示，以及剪枝，也都与归纳和猜想有关。

另外本题还可以转化为 01 背包问题，问题转化也是一个重要的思想。

题目

给你两个长度为 n 下标从 0 开始的整数数组 cost 和 time ，分别表示给 n 堵不同的墙刷油漆需要的开销和时间。你有两名油漆匠：

  • 一位需要 付费 的油漆匠，刷第 i 堵墙需要花费 time[i] 单位的时间，开销为 cost[i] 单位的钱。
  • 一位 免费 的油漆匠，刷 任意 一堵墙的时间为 1 单位，开销为 0 。但是必须在付费油漆匠 工作 时，免费油漆匠才会工作。

请你返回刷完 n 堵墙最少开销为多少。

提示：

1
2
3
4
1 <= cost.length <= 500
cost.length == time.length
1 <= cost[i] <= 1e6
1 <= time[i] <= 500

示例 1：
输入：cost = [1,2,3,2], time = [1,2,3,2]
输出：3
解释：下标为 0 和 1 的墙由付费油漆匠来刷，需要 3 单位时间。同时，免费油漆匠刷下标为 2 和 3 的墙，需要 2 单位时间，开销为 0 。总开销为 1 + 2 = 3 。

示例 2：
输入：cost = [2,3,4,2], time = [1,1,1,1]
输出：4
解释：下标为 0 和 3 的墙由付费油漆匠来刷，需要 2 单位时间。同时，免费油漆匠刷下标为 1 和 2 的墙，需要 2 单位时间，开销为 0 。总开销为 2 + 2 = 4 。

题解

我们要完成 n 堵墙，使得总成本最少。因此我们需要对刷墙顺序做合理调度，使得尽可能地使用免费油漆匠。

只有在付费油漆匠正在工作时，新的一堵墙才能给免费油漆匠，并且免费油漆匠的刷一堵墙的时间总是 1，总是小于等于付费油漆匠 (1 <= time[i] <= 500)。

因此从整体看，假设 $n$ 堵墙中有 $t$ 堵墙给了免费油漆匠，记其集合为 $A$，剩下的 $n-t$ 堵墙由付费油漆匠完成，及其集合为 $B$，那么 $A$ 中元素个数 $t$ 就不能大于 $B$ 中的总时间：

另一方面，如果可以从 $B$ 中取出一堵墙 $j_{0}$，剩余的集合记为 $C = B - \{j_{0}\}$，如果 $t + 1 \leq \sum\limits_{j\in C}time[j] = \sum\limits_{j\in B}time[j] - \min\limits_{j\in B}time[j]$，那么就可以将 $j_{0}$ 交给免费油漆匠，省去费用 $cost[j_{0}]$，取得更好结果。

因此如果 $A$，$B$ 如果想要是候选答案，必须要满足：

综上，我们要找到所有满足以上条件的子集 $B$，使得 $\sum\limits_{j\in B}cost[j]$ 最小。

问题在于对于给定的 $A$ 和 $B$，$j_{0}$ 的选择可能非常多，事先也不知道将哪个 $j_{0}$ 放入 $A$ 会更好，因此只能一个一个去考虑。

但这里还有一个更大的问题，如果通过枚举子集的方式找到所有可能的 $B$ 的话，$n \leq 500$ 的范围过大。

算法1：猜想、动态规划

猜想

结合前面的推导，我们发现限制选为付费的下标集合 $B$ 的选择的一个关键因素是 $T = \sum\limits_{j\in B}time[j]$ 以及免费的个数 $t = n - |B|$。

因此这里提出一个最重要的猜想：就是如果以 $i=0,1,\cdots,n-1$ 的顺序依次考虑是否将第 $i$ 堵墙选为付费的，并且以 $i$ 作为动态规划的阶段，那么再加上此前阶段中选为付费的总时间 $T$ 以及选为免费的个数 $t$，即可形成最优子结构。

但这里最优子结构并不明显，还需要继续分析。假设当前考虑到了第 $i$ 堵墙，前面已经考虑完的第 $0,1,\cdots,i-1$ 堵墙中，总共的付费时间为 $T$，免费个数为 $t$，后续的第 $i,i+1,\cdots,n-1$ 这些墙的最少开销是多少，将这个问题记为 $(i, T, t)$。现在考虑第 $i$ 堵墙是否免费：

  • 如果令第 $i$ 堵墙付费，那么问题变为 $(i + 1, T + time[i], t)$。
  • 如果令第 $i$ 堵墙免费，那么问题变为 $(i + 1, T, t + 1)$。

这里我们就发现最优子结构的影子了：如果推导顺序是 $i$ 从 $n-1$ 到 $0$，那么问题 $(i, T, t)$ 的答案就可以从已经推导过的子问题 $(i + 1, T + time[i], t)$ 和 $(i + 1, T, t + 1)$ 得到。

动态规划

定义 $dp[i][T][t]$ 表示已经付费的总时间为 $T$，免费的个数为 $t$ 的情况下，$i,i+1,\cdots,n-1$ 这些墙的最少开销。这样定义的话，答案为 $dp[0][0][0]$。初始值为 $i=n$ 的时候

  • 如果 $t \leq T$，则 $dp[n][T][t] = 0$；
  • 否则不是可行解，记为 $dp[n][T][t] = INF$。

状态转移方程如下：

DP的优化：优化状态表示

考虑状态 $(i, T, t)$，仅看状态表示中的两个附加信息维度 $(T, t)$。有两个可能的决策，状态分别转移到 $(T + time[i], t)$ 和 $(T, t + 1)$。

可以看到，不论怎么转移 $T$ 和 $t$ 始终都在，并且系数也均为 $1$ 不变，那么在转移前后 $T - t$ 的这部分自然也不变。而在初始状态，决定初始值的正是 $T - t$，而不是具体的 $T$ 和 $t$。这说明，在同一阶段 $i$ 下，对于不同的 $T$ 和 $t$，只要 $T - t$ 相同，那么作为子问题的答案就是一样的。

基于以上思路，考虑将第二和第三维度 $T$ 和 $t$ 变为一个维度 $d$，表示为 $T$ 和 $t$ 的差，也就是 $d = T - t$。这样对于状态 $(i, d)$，如果第 $i$ 个付费，则转移到 $(i + 1, d + time[i])$，如果免费，则转移到 $(i + 1, d - 1)$。

这样动态规划可以重新定义 $dp[i][d]$ 表示此前已经付费的总时间减去免费的个数（也可以理解为总时间）的差值为 $d$ 的情况下，$i,i+1,\cdots,n-1$ 这些墙的最小开销。这样定义的话，答案为 $dp[0][0]$。初始值仍然为 $i=n$ 的情况，如果 $d \geq 0$，那么 $dp[n][d] = 0$，否则 $dp[n][d] = INF$。

状态转移方程如下：

但这里注意，第二个维度 $d$ 有可能会小于 0，实现的时候，如果有必要可以考虑用哈希表维护第二个维度。

DP的优化：剪枝

如果 $d \geq n - i$，那么后续的 $i, i+1,\cdots,n-1$ 这 $n - i$ 个墙就都可以免费了，直接 $dp[i][d] = 0$ 即可。

代码 (Python)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution:
    def paintWalls(self, cost: List[int], time: List[int]) -> int:
        n = len(cost)
        INF = int(1e9)

        @lru_cache(int(1e8))
        def solve(i: int, d: int) -> int:
            if i == n:
                return 0 if d >= 0 else INF

            if d >= n - i:
                return 0

            return min(cost[i] + solve(i + 1, d + time[i]), solve(i + 1, d - 1))

        return solve(0, 0)

算法2：转化、动态规划

问题转化，01背包

将 $n$ 堵墙分为 $A$，$B$，分别表示免费刷和付费刷的两个集合。必须满足 $\sum\limits_{j\in B}time[j] \geq |A| = n - |B|$。

将上式变形为 $\sum\limits_{j\in B}(time[j] + 1) \geq n$，也就是把 $|B|$ 拆成 $|B|$ 个 $1$。

将 $time[i] + 1$ 视为物品体积，$cost[i]$ 视为物品价值，问题就转化为：从 $n$ 个物品中选择若干个，体积之和至少为 $n$，价值之和最小是多少。

动态规划

定义 $dp[i][j]$ 表示从 $0,1,\cdots,i$ 中选，体积之和至少为 $j$ 时，价值之和的最小值。这样定义的话，答案为 $dp[n-1][n]$。初始值出现在 $i=0$：

  • 如果 $time[0] + 1 < j$，则 $dp[0][j] = INF$；
  • 如果 $0 < j \leq time[0] + 1$，则 $dp[0][j] = cost[0]$；
  • 如果 $j \leq 0$，则 $dp[0][j] = 0$。

状态转移方程如下：

这里同样要注意，第二个维度 $j$ 可能为负数。

DP的优化：剪枝

当 $j \leq 0$ 时，可以一个都不选，这样直接 $dp[i][j] = 0$ 即可。

代码 (Python)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
from functools import lru_cache

class Solution:
    def paintWalls(self, cost: List[int], time: List[int]) -> int:
        n = len(cost)
        INF = int(1e9)

        @lru_cache(int(1e8))
        def solve(i: int, j: int) -> int:
            if i == 0:
                if time[0] + 1 < j:
                    return INF
                elif j <= 0:
                    return 0
                else:
                    return cost[0]

            if j <= 0:
                return 0

            return min(cost[i] + solve(i - 1, j - time[i] - 1), solve(i - 1, j))

        return solve(n - 1, n)
Share