算法疑难杂症

力扣LCP14-切分数组

字数统计: 1.5k字   |   阅读时长: 6分
, , ,

摘要: LCP14，分解质因数+哈希表优化DP

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

本文看一个分解质因数与动态规划结合的题。直接写出动态规划算法比较简单，但难点在于如何用分解质因数进行优化，一方面要引入哈希表，另一方面需要优化分解质因数的求法，非常综合的一道题。

力扣952-按公因数计算最大组件大小 的思想类似，是分解质因数与并查集结合的题目，把整个值域范围的数字在并查集中维护，在值域范围内进行素数筛，对每个得到的素数进行并查集操作，根据并查集的最终状态可以求出结果，可以对比着看。

题目

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

限制：

1
2
1 <= nums.length <= 1e5
2 <= nums[i] <= 1e6

示例 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
2
3
4
5
6
7
8
9
10
11
状态定义：
dp[i] := nums[0..i-1] 上最少可以切分的子数组个数

答案：
dp[n]

初始化：
dp[0] = 0

状态转移：
dp[i] = min{dp[j] + 1 | 0 <= j <= i-1 且 gcd(nums[j], nums[i-1]) > 1}

代码 (C++)

注：$O(N^{2})$ 超时。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
    int splitArray(vector<int>& nums) {
        int n = nums.size();
        vector<int> dp(n + 1, 0);
        for(int i = 1; i <= n; ++i)
        {
            dp[i] = 1 + dp[i - 1];
            for(int j = 0; j < i - 1; ++j)
            {
                if(gcd<int>(nums[j], nums[i - 1]) > 1)
                    dp[i] = min(dp[i], 1 + dp[j]);
            }
        }
        return dp[n];
    }
};

优化：哈希表优化DP + 分解质因数

在计算 dp[i] 时，dp[0] 到 dp[i - 1] 已经算好。考虑 nums[i - 1]，有以下两种情况：

  • nums[i - 1] 自己是一组，则 dp[i] = 1 + dp[i - 1]
  • nums[i - 1] 与 nums[0..i-2] 中的某个数 nums[j] 的公约数大于 1，则 dp[i] = 1 + dp[j]

不是每个 nums[0..i-2] 都需要算一遍。比如 nums[i - 1] = 2 * 2 * 3，那么其实只需要把 nums[0..i-2] 中包含质因数 2 或 3 的数字算一遍就行。

前面我们是枚举 0 <= j < i - 1，然后判断 gcd(nums[j], nums[i - 1]) 来做的。

这里我们枚举 nums[i - 1] 的每个质因数 p，在 0 <= j <= i - 1 范围内，如果 nums[j] 含有质因数 p，则 dp[j] 就可能对答案有贡献，更新 dp[i] = min(dp[i], 1 + dp[j])。

我们并不需要知道前面这一系列的 dp[j]，只需要知道这些 dp[j] 的最小值，记为 minx，然后直接更新 dp[i] = min(dp[i], 1 + minx) 即可。

此时状态转移方程变为：

这个转移方程形式可以通过哈希表优化，参考文章 哈希表优化DP。

在推导 DP 的过程中，可以维护一个哈希表 mapping，mapping[p] 表示 nums[0..i-i] 上含有质因数 p 的 nums[j] 中，dp[j] 的最小值。

分解质因数得到 factors 的算法，有基于试除法和基于素数筛两种，参考 素数筛。这里由于要对很多数分解质因数，可以用基于素数筛的方法。

代码 (C++)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
vector<int> get_primes(int n) {
    if(n < 2) return {};
    vector<bool> vec(n, true);
    vec[0] = false;
    vec[1] = false;
    int cnt = 0;
    vector<int> primes;
    for(int i = 2; i < n; ++i)
    {
        if(vec[i])
        {
            ++cnt;
            primes.push_back(i);
        }
        for(int j = 0; j < cnt && i * primes[j] < n; ++j)
        {
            vec[i * primes[j]] = false;
            if(i % primes[j] == 0)
                break;
        }
    }
    return primes;
}

class Solution {
public:
    int splitArray(vector<int>& nums) {
        int n = nums.size();
        int maxx = *max_element(nums.begin(), nums.end());
        vector<int> primes = get_primes(maxx + 1);
        vector<int> dp(n + 1, n + 1);
        dp[0] = 0;
        vector<int> mapping(maxx + 1, n + 1);
        vector<int> factors;
        for(int i = 1; i <= n; ++i)
        {
            for(int p: primes)
            {
                if(p > nums[i - 1])
                    break;
                if(nums[i - 1] % p == 0)
                {
                    mapping[p] = min(mapping[p], dp[i - 1]);
                    dp[i] = min(dp[i], 1 + mapping[p]);
                }
            }
        }
        return dp[n];
    }
};

优化：记录每个数的最小质因数

得到小于等于 maxx 的所有质数 primes 之后。按顺序枚举每个 p，对小于等于 maxx 的 2p, 3p, … 更新 min_factor，min_factor[x] 为 x 的最小质因数。

此后对于每个 nums[i - 1]，就可以按以下方式枚举它的所有质因数了：

1
2
3
4
5
for(int x = nums[i - 1]; x > 1; x /= min_factor[x])
{
    int p = min_factor[x];
    ...
}

代码 (C++)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
class Solution {
public:
    int splitArray(vector<int>& nums) {
        int n = nums.size();
        int maxx = *max_element(nums.begin(), nums.end());
        vector<int> primes = get_primes(maxx + 1);

        vector<int> min_factor(maxx + 1, 0);
        for(int p: primes)
        {
            min_factor[p] = p;
            for(int j = 2 * p; j <= maxx; j += p)
                if(min_factor[j] == 0)
                    min_factor[j] = p;
        }

        vector<int> dp(n + 1, n + 1);
        dp[0] = 0;
        vector<int> mapping(maxx + 1, n + 1);
        for(int i = 1; i <= n; ++i)
        {
            for(int x = nums[i - 1]; x > 1; x /= min_factor[x])
            {
                int p = min_factor[x];
                mapping[p] = min(mapping[p], dp[i - 1]);
                dp[i] = min(dp[i], 1 + mapping[p]);
            }
        }
        return dp[n];
    }
};
Share