Split Array问题：第二种递归解法的原理与递推关系解析

问题背景 #

给定整数数组nums和整数k，将nums分割为k个非空子数组（子数组为连续部分），要求最小化子数组的最大和，返回该最小化的最大和。

第一种解法：索引式递归的原理 #

这种解法通过**索引index**标记当前处理的起始位置，避免数组切割，递推逻辑清晰：

• 递归函数定义：recursive(nums, m, index) 表示从index开始的子数组，分割为m份时的最小最大和。
• 终止条件：当m=1时，直接返回从index到数组末尾的总和（只能分成1份，总和就是最大和）。
• 递推关系：遍历从index到nums.length - m的所有位置i（保证剩下的元素能分成m-1份），计算当前分割的子数组和sum（从index到i），然后递归计算剩下的部分（从i+1开始，分割为m-1份）的最小最大和，取两者的最大值（当前分割方案的最大和），再在所有可能的分割中取最小值，即为当前状态的解。
• 记忆化：用memo[m+index]缓存结果，避免重复计算。

第二种解法：数组切割式递归的原理 #

这种解法通过切割数组而非索引缩小问题规模，看似直观，实则和第一种解法的核心逻辑完全等价，只是问题的表达方式不同：

递归函数定义 #

splitArray(boards, k) 表示当前输入的数组boards，分割为k份时的最小最大和。

终止条件 #

当k=1时，直接返回当前数组的总和（只能分成1份，总和就是最大和）。

递推关系 #

遍历当前数组的所有分割点i（从0到数组末尾）：

1. 将当前数组分成两部分：前i个元素组成的子数组（boards.slice(0,i)），以及从i开始的剩余数组（boards.slice(i)）。
2. 计算前i个元素的和，同时递归计算剩余数组分割为k-1份的最小最大和。
3. 取这两个值的最大值——这代表选择当前分割点i时，整个分割方案的最大和。
4. 在所有分割点的结果中取最小值，就是当前数组分割为k份的最小最大和。

为什么循环范围调整后仍有效？ #

原代码中循环是i < boards.length，但实际上当i取到boards.length-1时，剩余数组是boards.slice(boards.length-1)（即最后一个元素），此时k-1必须至少为1，而因为递归中k会逐步减到1，只要初始k合法（1<=k<=数组长度），就能保证剩余数组非空。即使扩大循环范围，递归过程中也会因为终止条件和记忆化，不会出现错误，只是会多一些无效计算。

记忆化逻辑 #

用memo[boards.join('')+k]作为缓存键，将当前数组的字符串形式和k组合，缓存对应的最小最大和，避免重复计算相同的子问题。

两种解法的等价性 #

两种解法本质是同一思路的不同实现：

• 第一种用索引标记起始位置，避免数组切割，更高效（无需创建新数组）。
• 第二种用数组切割，更直观符合分割思维，但每次切割会创建新数组，性能略差。
• 核心递推逻辑一致：尝试所有可能的第一个分割点，计算当前分割的最大和，递归求解剩余部分的最小最大和，最终取所有方案的最小值。

代码对比 #

第一种解法（索引式递归） #

function splitArray(nums, m) {
    return recursive(nums, m, 0);
}
function recursive(nums, m, index, memo={}) {
    if(memo[''+m + index]) return memo[''+m + index];
    if(m === 1){
        let sum = 0;
        for(let i=index; i<nums.length; i++)
            sum += nums[i];
        return sum;
    }
    let min = Infinity;
    let sum = 0;
    for(let i=index; i<=nums.length-m; i++) {
        sum += nums[i];
        min = Math.min(min, Math.max(sum, recursive(nums, m-1, i+1, memo)));
    }
    memo[''+m + index] = min;
    return min;
}

第二种解法（数组切割式递归） #

function splitArray(boards, k, memo={}) {
    // Base Case
    if(memo[''+boards.join('')+k]) return memo[''+boards.join('')+k];
    if (k === 1) {
        return boards.reduce((sum, time) => sum + time, 0);
    }

    let minTime = Infinity;

    // Recursive Case
    for (let i = 0; i < boards.length; i++) {
        const timePartition = Math.max(
            boards.slice(0, i).reduce((sum, time) => sum + time, 0),
            splitArray(boards.slice(i), k - 1, memo)
        );
        minTime = Math.min(minTime, timePartition);
    }
    memo[''+boards.join('')+k] = minTime;
    return minTime;
}

内容的提问来源于stack exchange，提问作者ABGR