以下是 LeetCode LCP 14. 切分数组 的 Java 实现基于 质因数分解 动态规划 的经典解法。解题思路1. 预处理最小质因数用线性筛预处理出 110⁶ 每个数的最小质因数 minPrime[i]方便后续快速分解质因数2. 动态规划dp[i] 表示前 i 个数即 nums[0..i-1]能切分的最少数组个数3. 关键优化对每个质因数 p维护 pFlag[p] 表示以质因数 p 为桥梁连接时前序状态的最小值状态转移- 每个新数 nums[i] 要么单独成组dp[i1] dp[i] 1- 要么与前面某个有相同质因数的数组成一组找到前面有相同质因数的位置 j则 dp[i1] dp[j] 1javaclass Solution {// 预处理最小质因数线性筛private static final int MAX 1000000;private static int[] minPrime new int[MAX 1];private static boolean initialized false;private static void init() {if (initialized) return;// minPrime[i] 表示 i 的最小质因数for (int i 2; i MAX; i) {if (minPrime[i] 0) {// i 是质数for (int j i; j MAX; j i) {if (minPrime[j] 0) {minPrime[j] i;}}}}initialized true;}public int splitArray(int[] nums) {init();int n nums.length;// dp[i] 表示前 i 个数nums[0..i-1]能切分的最少数组个数int[] dp new int[n 1];// pFlag[p] 表示以质因数 p 为桥梁时前序状态的最小值// 初始化为一个较大值int[] pFlag new int[MAX 1];for (int i 0; i MAX; i) {pFlag[i] n; // 初始化为 n最大可能值}dp[0] 0; // 0个数需要0个子数组for (int i 1; i n; i) {int x nums[i - 1];// 默认情况当前数单独成一组dp[i] dp[i - 1] 1;// 分解 nums[i-1] 的所有质因数int temp x;while (temp 1) {int p minPrime[temp];// 找到之前出现过质因数 p 的位置// pFlag[p] 记录的是 dp[j] 的最小值其中 j 是前面某个以 p 为质因数的数的位置dp[i] Math.min(dp[i], pFlag[p] 1);// 更新 pFlag[p]当前位置 i-1 之前的状态 dp[i-1]// 注意这里存的是 dp[i-1]因为如果从 i 位置开始新的一组前面是 [0, i-2]pFlag[p] Math.min(pFlag[p], dp[i - 1]);// 去掉所有 p 因子while (temp % p 0) {temp / p;}}}return dp[n];}}关键点说明步骤 说明线性筛预处理 预处理 110⁶ 的最小质因数时间 O(MAX log log MAX)空间 O(MAX)质因数分解 利用 minPrime 数组每次除以最小质因数快速分解pFlag 数组 对每个质因数 p记录以 p 为桥梁时前序状态的最小 dp 值状态转移 dp[i] min(dp[i-1]1, min(pFlag[p]1))其中 p 是 nums[i-1] 的所有质因数复杂度分析- 时间复杂度O(MAX log log MAX n × log(nums[i]))其中 MAX 10⁶- 线性筛预处理O(MAX log log MAX)- 每个数分解质因数O(log nums[i])- 空间复杂度O(MAX n)主要是 minPrime 和 pFlag 数组示例验证输入: nums [2,3,3,2,3,3]输出: 2解释:- nums[0]2, 质因数2, pFlag[2]0, dp[1]1- nums[1]3, 质因数3, pFlag[3]1, dp[2]2- nums[2]3, 质因数3, pFlag[3]min(1,2)1, dp[3]min(3, pFlag[3]12)2- nums[3]2, 质因数2, pFlag[2]min(0,2)0, dp[4]min(3, pFlag[2]11)1- nums[4]3, 质因数3, pFlag[3]min(1,1)1, dp[5]min(2, pFlag[3]12)2- nums[5]3, 质因数3, pFlag[3]min(1,2)1, dp[6]min(3, pFlag[3]12)2最终 dp[6] 2对应 [2,3,3,2] 和 [3,3]
以下是 LeetCode LCP 14. 切分数组 的 Java 实现基于 质因数分解 动态规划 的经典解法。解题思路1. 预处理最小质因数用线性筛预处理出 110⁶ 每个数的最小质因数 minPrime[i]方便后续快速分解质因数2. 动态规划dp[i] 表示前 i 个数即 nums[0..i-1]能切分的最少数组个数3. 关键优化对每个质因数 p维护 pFlag[p] 表示以质因数 p 为桥梁连接时前序状态的最小值状态转移- 每个新数 nums[i] 要么单独成组dp[i1] dp[i] 1- 要么与前面某个有相同质因数的数组成一组找到前面有相同质因数的位置 j则 dp[i1] dp[j] 1javaclass Solution {// 预处理最小质因数线性筛private static final int MAX 1000000;private static int[] minPrime new int[MAX 1];private static boolean initialized false;private static void init() {if (initialized) return;// minPrime[i] 表示 i 的最小质因数for (int i 2; i MAX; i) {if (minPrime[i] 0) {// i 是质数for (int j i; j MAX; j i) {if (minPrime[j] 0) {minPrime[j] i;}}}}initialized true;}public int splitArray(int[] nums) {init();int n nums.length;// dp[i] 表示前 i 个数nums[0..i-1]能切分的最少数组个数int[] dp new int[n 1];// pFlag[p] 表示以质因数 p 为桥梁时前序状态的最小值// 初始化为一个较大值int[] pFlag new int[MAX 1];for (int i 0; i MAX; i) {pFlag[i] n; // 初始化为 n最大可能值}dp[0] 0; // 0个数需要0个子数组for (int i 1; i n; i) {int x nums[i - 1];// 默认情况当前数单独成一组dp[i] dp[i - 1] 1;// 分解 nums[i-1] 的所有质因数int temp x;while (temp 1) {int p minPrime[temp];// 找到之前出现过质因数 p 的位置// pFlag[p] 记录的是 dp[j] 的最小值其中 j 是前面某个以 p 为质因数的数的位置dp[i] Math.min(dp[i], pFlag[p] 1);// 更新 pFlag[p]当前位置 i-1 之前的状态 dp[i-1]// 注意这里存的是 dp[i-1]因为如果从 i 位置开始新的一组前面是 [0, i-2]pFlag[p] Math.min(pFlag[p], dp[i - 1]);// 去掉所有 p 因子while (temp % p 0) {temp / p;}}}return dp[n];}}关键点说明步骤 说明线性筛预处理 预处理 110⁶ 的最小质因数时间 O(MAX log log MAX)空间 O(MAX)质因数分解 利用 minPrime 数组每次除以最小质因数快速分解pFlag 数组 对每个质因数 p记录以 p 为桥梁时前序状态的最小 dp 值状态转移 dp[i] min(dp[i-1]1, min(pFlag[p]1))其中 p 是 nums[i-1] 的所有质因数复杂度分析- 时间复杂度O(MAX log log MAX n × log(nums[i]))其中 MAX 10⁶- 线性筛预处理O(MAX log log MAX)- 每个数分解质因数O(log nums[i])- 空间复杂度O(MAX n)主要是 minPrime 和 pFlag 数组示例验证输入: nums [2,3,3,2,3,3]输出: 2解释:- nums[0]2, 质因数2, pFlag[2]0, dp[1]1- nums[1]3, 质因数3, pFlag[3]1, dp[2]2- nums[2]3, 质因数3, pFlag[3]min(1,2)1, dp[3]min(3, pFlag[3]12)2- nums[3]2, 质因数2, pFlag[2]min(0,2)0, dp[4]min(3, pFlag[2]11)1- nums[4]3, 质因数3, pFlag[3]min(1,1)1, dp[5]min(2, pFlag[3]12)2- nums[5]3, 质因数3, pFlag[3]min(1,2)1, dp[6]min(3, pFlag[3]12)2最终 dp[6] 2对应 [2,3,3,2] 和 [3,3]
