题解 Leetcode LCP.14 切分数组

题目

给定一个整数数组 nums ，小李想将 nums 切割成若干个非空子数组，使得每个子数组最左边的数和最右边的数的最大公约数大于 1 。为了减少他的工作量，请求出最少可以切成多少个子数组。

示例 1：

输入：nums = [2,3,3,2,3,3]

输出：2

解释：最优切割为 [2,3,3,2] 和 [3,3] 。第一个子数组头尾数字的最大公约数为 2 ，第二个子数组头尾数字的最大公约数为 3 。

示例 2：

输入：nums = [2,3,5,7]

输出：4

解释：只有一种可行的切割：[2], [3], [5], [7]

限制：

1 <= nums.length <= 10^5 2 <= nums[i] <= 10^6 通过次数 1,872 提交次数 10,478

来源：力扣（LeetCode）链接：https://leetcode-cn.com/problems/qie-fen-shu-zu 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路

注意到nums.length>=1，所以从长度为 1 起分析，记L=nums.length，记答案为ANS，记a&b=gcd(a, b)>1，其中gcd即为求最大公约数的函数。

1. 当L==1时，显然ANS=1。
2. 当L==2时，记该串为ab，则ANS = a&b ? 1 : 2。
3. 现在分析L==3时的情况。当L==3时，记串为abc，若a&b，则ANS=1；否则若a&b || b&c，则ANS=2；否则，ANS=3。

为一般化，我们记该串为$a_1a_2a_3\dots a_n$，记$f(a_1a_2a_3\dots a_n) = f(n)$为该串能切分的最小子数组个数。

显然，我们需要找出一个递推关系（减而治之）或者归并关系（分而治之）。

首先探求$f(a_1a_2a_3\dots a_n)$与$f(a_1a_2a_3\dots a_{n-1})$之间是否存在关系。

1. 当$a_n=a_{n-1}$时，我们很容易得到$f(a_1a_2a_3\dots a_n) = f(a_1a_2a_3\dots a_{n-1})$，因为无论$f(n-1)$等于 1 还是其它， 它都可以写成多个子数组的形式，其中最后一个子数组的末尾就是$a_{n-1}$,也即$a_{n-1}$和最后一个子数组的第一个数（或者它本身）满足非互质的条件。于是同样可以得到这个数与$a_n$依旧非互质，不会改变原先的结果。所以$f(n) = f(n-1)$。
2. 难的是$a_n\neq a_{n-1}$的场景。最简单的可能是$a_n=a_1$，于是这个串的总长结果就为 1，皆大欢喜。但我们必须着手分析当$a_n\neq a_{n-1} \ \&\ a_n \neq a_1$的情况。此时，也有最简单的一种可能，即$a_n$与左边$n-1$个数全部互质，显然，此时$f(n)=f(n-1)+1$。尽管这一点的得出是很容易的，但却仿佛蕴含着什么不可告人的秘密。
3. 现在假设不是全互质，而是有一个互质，此时我们不妨令串为$a_1\dots c_1 b1 d_1\dots e_1b_n$，即$b1$和$b_n$是非互质的，很显然，它们可以合成一个子数组，而一旦合并成子数组，从$b_1$到$b_n$中的$d_1\dots e_1$这一串就等于完全消掉了，于是$f(a_1\dots c_1 b1 d_1\dots e_1b_n) <= f(a_1\dots c_1)+1$，这是显然的，同时$f(a_1\dots c_1 b1 d_1\dots e_1b_n) <= f(a_1\dots c_1 b_1 d_1\dots e_1)+1$也是显然的。这就是一个很有用的递推关系了，我们待会还要用到，但要注意此时我们尚未能够知道$f(a_1\dots c_1)$和$f(a_1\dots c_1 b_1 d_1\dots e_1)$之间的关系。
4. 刚刚只是推导出了一个上限，我们还得知道下限。当我们拿到$b_n$的时候，如果我们什么也不做（即独立成组），则导致$f$增一，与目标需求是不合的。因此我们必然需要往前搜索，尝试将$b_n$与某个数组合成一组，看看能不能将整体目标值降下来。但和谁组呢？一个自然的想法是和$b_i$组，即与和自己非互质的数组成一组后，会变成$f(a_1\dots c_1)+1$的结果，如果恰好$c_1=a_1$的话，答案就是 2 了，肯定没有比这个更优的结果了，因为$a_1$和$b_n$互质，否则答案直接变成 1 了。
5. 但是$b_n$必然要和自己非互质的数（设为$b_i$）一组吗？这是一个听起来有点荒诞的问题，难道$b_n$还能有其他选择吗？但我们或许可以给它一次机会，看看它能兴出什么风，作出什么浪来。我们假设它去选择和$c_i$一组，这样的话，就把原数组分成两个子数组，左边是$a_1$到$c_i$的左边，右边是$c_i$到$b_n$，此时能够让整体更优吗？但是它既然想这么干的话，肯定有它自己的想法，我们估摸着猜一下，当它觉从$c_i$处一刀切下来后，我们顺势就势，令原先$f(n-1)$的构成就为$a_1$到$c_1$的左边，这样左边一部分能切割出的子数组个数就相等了。然后看右边，右边原先是$c_i$到$b_n$的左边，这边假设原先最少能够分成$k$个数组，现在多了一个$b_n$，让这个子数组的个数能够减下来，那显然是因为这一串里面有个$b_i$，它能和$b_n$有机结合，于是让这个子数组的个数变成$c_1$到$b_i$的左边再加上 1，于是我们立即可以知道，如果是这样的话，为什么我们不直接在$b_i$的左边来一刀呢？（也就是和自己非互质的数为一组）这样能够保证子数组个数不会大于在任意一个数$c_i$上来一刀。
6. 基于以上的分析，我们知道了，每当加入一个$b_n$后，新的整体最优方案，必然从每个与$b_n$非互质的$b_i$处产生，只需在这儿来上一刀，整体就能变成$f(b_i-1)+1$，例如$b_i$左边就是与$a_1$非互质的数，则答案立即锐减到了 2，而除去此种办法，别无其他更好的办法有效降低最终子数组的个数了。这是解决本题最关键的一点：分而治之的点必然在与$b_n$之前非互质的点中产生，于是结果就是$min\{f(b_i-1)\}+1$。
7. 基于第 6 点我们已经能够写出$O(n^2)$复杂度的算法，每个点找其所有的“前缀”（前面 k 个$b_i$），求其 k 个子串中所能得到的最小子数组个数，然后加一。但是对于 AC 本题还是不够的。我们需要进一步分析。事实上刚刚我们通过减而治之入手，最后通过分而治之找到了解题的突破口，现在我们需要回到减而治之，再从更宏观的角度去探索可供优化的空间了，那就是dp 状态转移方程！
8. 我们最终要解决的是一个$a_1\dots b_n$的切分问题，而切分的点都在$b_i$上，假设$b_n$中不存在$b_i$呢？那显然$f(n)=f(n-1)$，这就是我们的第一个方程。接着，假设有一个$b_i$，例如串为$a_1\dots c_1b1\dots c_nb_n$，基于以上那么多那么多的分析，我们知道$f(n)=min\{f(c_1), f(c_n)\}+1$，但如果我们仔细看一下，这个式子还可以写成$f(n)=min\{f(c_1)+1, f(c_n)+1\}$，也即$f(n)=min\{f(b_1), f(c_n)+1\}$，这难道不就是我们再熟悉不过的转移方程吗？也就是说，每个$b_n$只与上一个$b_{n-1}$时的状态和上一个元素$c_{n-1}$时的状态有关！毫无疑问，我们可以通过一个一维数组$dp$记录每个点的状态，然后$O(n)$一趟完成遍历即可！这就是本题第二个最关键的点：每个$b_n$只与$b_{n-1}$和$c_{n-1}$的状态有关，即$f(b_n)=min\{f(b_{n-1}, f(c_{n-1})+1\}$因此只需要通过一个一维数组 dp 记录每个点的状态即可。
9. 我们现在来到了最后一个问题，如何从$b_n$得到上一个$b_{n-1}$呢？很显然，暴力搜索是可以实现的，只不过效率太低。或者，我们在程序的开始，就直接算出$n*(n-1)/2$个元素之间的彼此是否互质关系，只不过效率依旧不高。其实我们不妨再思考一下，由于$b_n$只和上一个$b_{n-1}$和$c_{n-1}$有关，因此我们只需要对于每个$b_i$倒序搜索到第 $b_{i-1}$个就可以，不用把所有的元素都给乘一遍。尽管如此，我们的效率依旧不是很高，因为每个$c_{n-1}$也要去乘，这样，这就是一个链，几乎还是每个元素都乘一遍，尤其是那些可能与所有元素都不互质的元素来说。我们不禁重新思考这个$c_{n-1}$的意义。
10. 【看题解，要结合质数筛】