https://leetcode.cn/problems/qie-fen-shu-zu/description/
给定一个整数数组 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 首先想到动态规划转移方程
dp[x]为索引x 可以分成的最小组数
dp[i] = dp[j-1]+1; == 如果nums[i] nums[j]最大公约数不为1(用其他质因数) 那么nums[i] nums[j]划分为一组。
2 但是上面的时间复杂度是O(n^2)
优化为 判断dp[i]的时候 记录前边和他有相同质因数的nums[j]最小分成组数
dp[i] = min(PrimesMinLen[primesV]+1);
分解质因数为sqrt(x);
时间复杂度为O(n *sqrt(x))
class Solution {
public:
int dp[100010];
unordered_map<int ,int> PrimesMinLen;
int splitArray(vector<int>& nums) {
memset(dp, 0x3f, sizeof dp);
//拆入一个质数 不可能和其他数 分组。 后面索引从1开始计算 避免一些边界问题
nums.insert(nums.begin(), 100019);
dp[0] = 0;
for (int i = 1; i < nums.size(); i++) {
dp[i] = dp[i - 1] + 1; //另开一个数组
//分解质因数
int splitP[20]; memset(splitP, 0, sizeof splitP);
int splitCnt = 0;
for (int j = 2; j <= nums[i] / j; j++) {
while (nums[i] % j == 0) {
nums[i] /= j;
splitP[splitCnt] = j;
}
if (splitP[splitCnt] != 0) {
int primesV = splitP[splitCnt]; splitCnt++;
if (PrimesMinLen.count(primesV) != 0)
dp[i] = min(dp[i], PrimesMinLen[primesV]+1);
}
}
if (nums[i] != 1) {
splitP[splitCnt] = nums[i]; splitCnt++;
int primesV = nums[i];
if(PrimesMinLen.count(primesV) !=0)
dp[i] = min(dp[i], PrimesMinLen[primesV]+1);
}
//更新 该元素左端的元素 质数对应的最短分组
for (int j = 0; j < splitCnt; j++) {
int primesV = splitP[j];
if (PrimesMinLen.count(primesV) == 0) PrimesMinLen[primesV] = dp[i-1];
else PrimesMinLen[primesV] = min(PrimesMinLen[primesV], dp[i-1]);
}
}
return dp[nums.size() - 1];
}
};