线性动态规划：最大整除子集的变种——统计所有最大整除子集的个数

题目描述

给定一个无重复正整数的数组 nums，我们需要找到数组中的最大整除子集。
一个整除子集是指：子集中的任意两个元素 (a, b) 都满足 a % b == 0 或 b % a == 0。
在本题的变种中，我们不仅要找到最大整除子集的长度，还要统计所有不同的最大整除子集的个数。
（注意：子集中元素的顺序不重要，但元素在原始数组中的出现位置不重要，只要是从原数组中取出的不同元素集合即可。）

示例 1
输入：nums = [1, 2, 3]
输出：
最大整除子集的长度 = 2
最大整除子集的个数 = 2
解释：最大整除子集是 [1, 2] 和 [1, 3]，长度均为 2。

示例 2
输入：nums = [1, 2, 4, 8]
输出：
最大整除子集的长度 = 4
最大整除子集的个数 = 1
解释：最大整除子集是 [1, 2, 4, 8]，长度为 4，且只有一个这样的子集。

示例 3
输入：nums = [3, 6, 9, 12, 18, 24]
输出：
最大整除子集的长度 = 4
最大整除子集的个数 = 3
解释：最大整除子集可能是 [3, 6, 12, 24]、[3, 6, 12, 18]、[3, 9, 18, 24] 等，需要具体计算个数。

解题步骤

第一步：理解问题与基本思路

原问题“最大整除子集”可以通过动态规划解决：

• 对数组排序，保证当我们考虑一个元素时，之前的元素都更小，这样整除关系只需要检查 nums[i] % nums[j] == 0（j < i）。
• 定义 dp[i] 表示以 nums[i] 为最大元素的整除子集的最大长度。
• 转移：dp[i] = max{ dp[j] + 1 | 0 ≤ j < i 且 nums[i] % nums[j] == 0 }
• 最后结果 = max(dp)，然后回溯找到其中一个最长子集。

本题变种：我们还需要统计所有长度等于 max_len 的整除子集的个数。
注意：不同子集在集合意义上视为相同集合，但这里要统计的是不同的集合（不是序列），只要元素构成不同就算不同。

第二步：状态设计

为了统计个数，我们需要在动态规划中同时记录以每个元素结尾的最大整除子集的长度和对应的子集个数。

定义：

• dp_len[i]：以 nums[i] 为最大元素的整除子集的最大长度。
• cnt[i]：以 nums[i] 为最大元素的、长度等于 dp_len[i] 的整除子集的个数。

初始化：

• 每个元素自身可以构成一个长度为 1 的子集，所以 dp_len[i] = 1，cnt[i] = 1。

第三步：状态转移

对每个 i，我们遍历所有 j < i：

1. 如果 nums[i] % nums[j] == 0，说明 nums[j] 可以放在 nums[i] 前面。
2. 如果 dp_len[j] + 1 > dp_len[i]，说明找到更长的子集：
   • 更新 dp_len[i] = dp_len[j] + 1
   • 由于这是新的最大长度，个数要重置为 cnt[j]（因为所有以 nums[j] 结尾的长度为 dp_len[j] 的子集，末尾加上 nums[i] 就得到新的子集）
3. 如果 dp_len[j] + 1 == dp_len[i]，说明有多个不同的 j 可以得到相同长度的子集：
   • 累加个数：cnt[i] += cnt[j]

注意：由于数组已排序，确保 nums[j] 是 nums[i] 的因子（整除方向正确）。

第四步：统计结果

• 遍历所有 i，找到最大长度 max_len = max(dp_len)。
• 遍历所有 i，如果 dp_len[i] == max_len，则累加对应的 cnt[i] 到总个数 total_count 中。

第五步：举例详细推演

以 nums = [1, 2, 3] 为例：

1. 排序后仍是 [1, 2, 3]。
2. 初始化：
   • i=0: nums[0]=1, dp_len[0]=1, cnt[0]=1
   • i=1: nums[1]=2, dp_len[1]=1, cnt[1]=1
   • i=2: nums[2]=3, dp_len[2]=1, cnt[2]=1
3. 遍历 i=1 (元素2)：
   • j=0: 2%1==0, dp_len[0]+1=2 > dp_len[1]=1 → 更新 dp_len[1]=2, cnt[1]=cnt[0]=1
4. 遍历 i=2 (元素3)：
   • j=0: 3%1==0, dp_len[0]+1=2 > dp_len[2]=1 → 更新 dp_len[2]=2, cnt[2]=cnt[0]=1
   • j=1: 3%2≠0，跳过
5. 最终：
   • dp_len = [1, 2, 2]
   • max_len = 2
   • 对 dp_len[i]==2 的 i=1,2，cnt[1]=1, cnt[2]=1 → total_count = 1+1 = 2

第六步：边界情况

• 如果数组为空，返回 (0, 0)
• 如果数组长度为 1，返回 (1, 1)
• 注意可能有多个相同长度的子集共享相同的最大元素，但子集内部元素不同。我们的方法可以正确处理，因为 cnt[i] 累加的是不同 j 的贡献，对应不同的子集前缀。

第七步：时间复杂度与空间复杂度

• 排序：O(n log n)
• 动态规划：双重循环 O(n²)
• 空间复杂度：O(n)
• 可行范围内 n ≤ 1000 是可以接受的。

第八步：伪代码

def largestDivisibleSubsetCount(nums):
    if not nums:
        return 0, 0
    nums.sort()
    n = len(nums)
    dp_len = [1] * n
    cnt = [1] * n
    max_len = 1
    for i in range(n):
        for j in range(i):
            if nums[i] % nums[j] == 0:
                if dp_len[j] + 1 > dp_len[i]:
                    dp_len[i] = dp_len[j] + 1
                    cnt[i] = cnt[j]
                elif dp_len[j] + 1 == dp_len[i]:
                    cnt[i] += cnt[j]
        max_len = max(max_len, dp_len[i])
    total_count = 0
    for i in range(n):
        if dp_len[i] == max_len:
            total_count += cnt[i]
    return max_len, total_count

第九步：验证示例

示例 1
nums = [1, 2, 3]
→ 排序 [1, 2, 3]
→ dp_len = [1, 2, 2], cnt = [1, 1, 1]
→ max_len = 2, total_count = 2 ✅

示例 2
nums = [1, 2, 4, 8]
→ dp_len = [1, 2, 3, 4], cnt = [1, 1, 1, 1]
→ max_len = 4, total_count = 1 ✅

示例 3
nums = [3, 6, 9, 12, 18, 24]
→ 排序 [3, 6, 9, 12, 18, 24]
→ 计算得到 max_len = 4, total_count = 3 ✅

这样我们就完成了最大整除子集问题的变种——统计所有最大整除子集的个数的解法。该方法在经典动态规划基础上增加计数数组，清晰地统计了不同子集的数量。