所有测试用例均通过以下是 LeetCode LCP 14. 切分数组 的 Python3 实现pythonfrom typing import List# Precompute minimum prime factor for each number up to 10^6# Using linear sieve (Euler sieve) for efficiencyMAX_N 10**6 1min_prime [0] * MAX_Nfor i in range(2, MAX_N):if min_prime[i] 0:min_prime[i] iif i * i MAX_N:for j in range(i * i, MAX_N, i):if min_prime[j] 0:min_prime[j] iclass Solution:def splitArray(self, nums: List[int]) - int:DP Prime FactorizationLet pre dp[i-1] minimum subarrays for nums[0..i-1]For nums[i], two options:1. nums[i] alone as a subarray: cur pre 12. nums[i] extends some previous subarray [j..i] where gcd(nums[j], nums[i]) 1This requires nums[j] and nums[i] share a common prime factor p.Then cur min(f[p] 1) where f[p] min dp[j-1] for j with prime factor p.After computing cur, update f[p] min(f[p], pre) for all prime factors p of nums[i].# f[p] minimum dp[j-1] for all positions j where nums[j] has prime factor pf {}pre 0 # dp[-1] 0 (empty prefix)for num in nums:# Option 1: num forms a new subarray by itselfcur pre 1# Option 2: num extends a previous subarray [j..i]# Find minimum f[p] for all prime factors p of numx numwhile x 1:p min_prime[x]if p in f:cur min(cur, f[p] 1)while x % p 0:x // p# Update f[p] with pre (dp[i-1]) for nums prime factors# For future nums[k], if they share prime factor p with num,# they can form subarray [current_pos..k], using pre as dp[j-1]x numwhile x 1:p min_prime[x]if p not in f:f[p] preelse:f[p] min(f[p], pre)while x % p 0:x // ppre curreturn pre核心思路这道题是 质因数分解 动态规划 的经典组合。1. 问题转化每个子数组要求 首尾元素的最大公约数 1即它们必须共享至少一个质因子。因此问题转化为找到一种切分方式使得相邻切分点之间能通过质因子链式连接。2. 关键观察- gcd(a, b) 1 ⟺ a 和 b 有共同的质因子- 如果子数组 [j..i] 是合法的则 nums[j] 和 nums[i] 必须共享质因子- 那么 dp[i] min(dp[i-1] 1, min(dp[j-1] 1))其中 gcd(nums[j], nums[i]) 13. 状态设计变量 含义pre dp[i-1]前 i-1 个数的最少子数组数f[p] 所有具有质因子 p 的位置 j 中dp[j-1] 的最小值cur dp[i]当前位置的最少子数组数4. 转移方程cur pre 1 # nums[i] 单独成组cur min(cur, f[p] 1) for all prime p | nums[i] # nums[i] 与前面某数同组处理完 nums[i] 后更新 f[p] min(f[p], pre)供后续数字使用。5. 质因数分解预处理用 线性筛欧拉筛 预处理 min_prime[x]x 的最小质因子可在 O(log x) 时间内分解任意数。复杂度分析复杂度预处理 O(M log log M)M 10⁶时间 O(n · log(max(nums)))每次分解质因数空间 O(M) 预处理 O(质因子种类) DP验证结果测试用例 输入 输出1 [2, 3, 3, 2, 3, 3] 2 ✅2 [2, 3, 5, 7] 4 ✅3 [2] 1 ✅4 [6, 10, 15] 1 ✅5 [4, 6, 9] 2 ✅6 [10, 6, 15] 1 ✅下载文件: [LCP 14 切分数组 Python3 实现](sandbox:///mnt/agents/output/lcp14_qie_fen_shu_zu.py) Kimi LeetCode LCP 14. 切分数组 Python3实现
所有测试用例均通过以下是 LeetCode LCP 14. 切分数组 的 Python3 实现pythonfrom typing import List# Precompute minimum prime factor for each number up to 10^6# Using linear sieve (Euler sieve) for efficiencyMAX_N 10**6 1min_prime [0] * MAX_Nfor i in range(2, MAX_N):if min_prime[i] 0:min_prime[i] iif i * i MAX_N:for j in range(i * i, MAX_N, i):if min_prime[j] 0:min_prime[j] iclass Solution:def splitArray(self, nums: List[int]) - int:DP Prime FactorizationLet pre dp[i-1] minimum subarrays for nums[0..i-1]For nums[i], two options:1. nums[i] alone as a subarray: cur pre 12. nums[i] extends some previous subarray [j..i] where gcd(nums[j], nums[i]) 1This requires nums[j] and nums[i] share a common prime factor p.Then cur min(f[p] 1) where f[p] min dp[j-1] for j with prime factor p.After computing cur, update f[p] min(f[p], pre) for all prime factors p of nums[i].# f[p] minimum dp[j-1] for all positions j where nums[j] has prime factor pf {}pre 0 # dp[-1] 0 (empty prefix)for num in nums:# Option 1: num forms a new subarray by itselfcur pre 1# Option 2: num extends a previous subarray [j..i]# Find minimum f[p] for all prime factors p of numx numwhile x 1:p min_prime[x]if p in f:cur min(cur, f[p] 1)while x % p 0:x // p# Update f[p] with pre (dp[i-1]) for nums prime factors# For future nums[k], if they share prime factor p with num,# they can form subarray [current_pos..k], using pre as dp[j-1]x numwhile x 1:p min_prime[x]if p not in f:f[p] preelse:f[p] min(f[p], pre)while x % p 0:x // ppre curreturn pre核心思路这道题是 质因数分解 动态规划 的经典组合。1. 问题转化每个子数组要求 首尾元素的最大公约数 1即它们必须共享至少一个质因子。因此问题转化为找到一种切分方式使得相邻切分点之间能通过质因子链式连接。2. 关键观察- gcd(a, b) 1 ⟺ a 和 b 有共同的质因子- 如果子数组 [j..i] 是合法的则 nums[j] 和 nums[i] 必须共享质因子- 那么 dp[i] min(dp[i-1] 1, min(dp[j-1] 1))其中 gcd(nums[j], nums[i]) 13. 状态设计变量 含义pre dp[i-1]前 i-1 个数的最少子数组数f[p] 所有具有质因子 p 的位置 j 中dp[j-1] 的最小值cur dp[i]当前位置的最少子数组数4. 转移方程cur pre 1 # nums[i] 单独成组cur min(cur, f[p] 1) for all prime p | nums[i] # nums[i] 与前面某数同组处理完 nums[i] 后更新 f[p] min(f[p], pre)供后续数字使用。5. 质因数分解预处理用 线性筛欧拉筛 预处理 min_prime[x]x 的最小质因子可在 O(log x) 时间内分解任意数。复杂度分析复杂度预处理 O(M log log M)M 10⁶时间 O(n · log(max(nums)))每次分解质因数空间 O(M) 预处理 O(质因子种类) DP验证结果测试用例 输入 输出1 [2, 3, 3, 2, 3, 3] 2 ✅2 [2, 3, 5, 7] 4 ✅3 [2] 1 ✅4 [6, 10, 15] 1 ✅5 [4, 6, 9] 2 ✅6 [10, 6, 15] 1 ✅下载文件: [LCP 14 切分数组 Python3 实现](sandbox:///mnt/agents/output/lcp14_qie_fen_shu_zu.py)