将整数拆分为唯一部分以最大化乘积的求解问题

问题描述 #

给定正整数N，将其拆分为互不重复的正整数之和，要求这些数的乘积最大，最终找出所有符合条件的拆分部分。
示例：

N = 8，最优拆分结果为 3 5，乘积为15（是所有合法拆分中的最大值）
N = 100，最优拆分结果为 2 3 5 6 7 8 9 10 11 12 13 14

动态规划解法思路 #

状态定义

我们定义dp[i]为一个二元组：

• 第一个元素：拆分数字i能得到的最大乘积
• 第二个元素：对应这个最大乘积的拆分数字列表（所有数字互不重复）

初始状态

• dp[0] = (1, [])：数字0无需拆分，乘积为1（作为乘法单位元），拆分列表为空
• dp[1] = (1, [1])：数字1只能拆分为自身，乘积为1

状态转移

对于每个从2到N的整数i，我们遍历所有可能的拆分项j（范围1到i//2，避免重复计算）：

1. 检查j是否不在dp[i-j]的拆分列表中（保证数字唯一）
2. 计算当前拆分的乘积：j * dp[i-j][0]
3. 如果该乘积大于当前记录的最大乘积，则更新最大乘积，并将j加入dp[i-j]的拆分列表，作为当前i的最优拆分方案
4. 同时对比不拆分（即直接取i本身）的情况，确保不会遗漏可能的最优解

示例推演（以N=8为例）

• dp[2]：可选拆分[2]（乘积2）或1+1（重复无效），最终dp[2]=(2, [2])
• dp[3]：可选拆分[3]（乘积3）或1+2（乘积2），最终dp[3]=(3, [3])
• dp[4]：可选拆分[4]（乘积4）、1+3（乘积3），最终dp[4]=(4, [4])
• dp[5]：可选拆分2+3（乘积6）、[5]（乘积5）、1+4（乘积4），最终dp[5]=(6, [2,3])
• dp[8]：遍历所有可能拆分后，发现3+5的乘积15最大，因此dp[8]=(15, [3,5])，与示例一致

额外优化思路（数学辅助） #

从数学角度看，最优拆分的数字通常是连续的正整数（从2开始），因为连续数的乘积增长效率最高，且天然避免重复。如果连续数的总和超过N，就从最大的数开始调整：

1. 先计算从2开始的连续数之和，直到总和接近N
2. 若总和大于N，逐步减去多余的数值（优先去掉小的数，避免重复）；若总和小于N，将剩余数值加到最大的数上
   比如N=100，从2开始的连续数2+3+4+...+14的和为104，比100多4，因此去掉4，得到拆分列表2 3 5 6 ... 14，与示例完全一致

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