2026-06-27：拆分到 1 的最小总代价。用go语言，给定一个整数 n。你需要把它不断地“拆分”为若干个 1，最后一共得到 n 个 1。 一次操作

2026-06-27：拆分到 1 的最小总代价。用go语言，给定一个整数 n。你需要把它不断地“拆分”为若干个 1，最后一共得到 n 个 1。

一次操作允许：把当前某个数 x 拆成两个正整数 a 和 b，满足 a + b = x。

这次操作的费用为 a × b。

你的目标是：在所有拆分方式中，计算从 n 逐步拆到 n 个 1 的最小“总费用”（把每一步的费用加起来）。

1 <= n <= 500。

输入： n = 3。

输出： 3。

解释：

一种最优的操作方案为：

a

b

a + b

a * b

代价

3

1

2

3

2

2

2

1

1

2

1

1

因此，最小总代价为 2 + 1 = 3。

题目来自力扣3857。

一、题意完整拆解 1. 操作规则

给定数字n，最终要拆成n个数字 1，全程只允许一种操作：
任选一个现有数字x，拆成两个正整数a、b，满足a + b = x；
单次拆分操作产生代价 =a × b；
总代价 = 每一步拆分代价全部累加，求所有拆分方案里最小总代价。

2. 样例 n=3 分步推演

初始状态：集合只有 [3]，总代价=0

第1步：拆分数字3

可选拆分组合只有(1,2)
单次代价：1×2=2，总代价更新为 0+2=2
当前数字集合：[1,2]，剩余未拆完的数是2

第2步：拆分数字2

只能拆成(1,1)
单次代价：1×1=1，总代价更新为 2+1=3
当前数字集合：[1,1,1]，全部是1，拆分结束
总代价结果：3，和题目输出一致。

二、推导最小总代价通用公式n*(n-1)/2（核心推理过程） 步骤1：先证明「任意数字x拆分到全部1，固定总代价，和拆分顺序无关」

假设数字 x，无论你怎么分、先分大的还是先分小的，最终把x拆成x个1的全部步骤代价之和永远固定。
举两个例子验证：

例1：x=4

方案1（逐层拆1）：
4→1+3，代价3；3→1+2，代价2；2→1+1，代价1；总和=3+2+1=6
方案2（对半拆分）：
4→2+2，代价4；第一个2拆1+1代价1；第二个2拆1+1代价1；总和=4+1+1=6
两种拆分顺序总代价完全相等。

步骤2：数学归纳推导固定总代价公式

对数字 x，拆为全部1的总代价恒等于x*(x-1)/2

• 基础边界：x=2，2×1/2=1，和实际拆分代价一致；

• 假设：所有小于x的数字k，拆分总代价为k(k-1)/2；

• 拆分x=a+b：本次代价a*b，后续a、b各自拆成1的代价分别是a(a-1)/2、b(b-1)/2
总代价 = ab + a(a-1)/2 + b(b-1)/2
化简：

ab + a(a-1)/2 + b(b-1)/2
= (2ab + a² -a + b² -b)/2
= (a² + 2ab + b² – a – b)/2
= [(a+b)² – (a+b)] / 2
令 x=a+b，代入得x(x-1)/2
归纳成立，证明：任意数字x拆分至全部1的总代价唯一固定，不存在更大/更小，题目所谓最小代价本质只有唯一值。

步骤3：代入样例 n=3 验证公式

3×(3-1)/2 = 3，与样例输出完全匹配。

三、程序执行完整流程（对应提供的Go代码）

1. 程序入口main函数启动，定义输入变量n=3；

2. 调用函数minCost(n)计算总代价：
函数内部执行数学公式n*(n-1)/2直接计算结果；

3. 将计算结果赋值给变量result；

4. 通过fmt.Println打印结果，输出数字3；

5. 程序执行完毕退出。

四、时间复杂度分析 1. 算法逻辑层面

核心计算仅一次乘法、一次减法、一次除法，属于常数级运算，运算次数和输入n的大小（1≤n≤500）无关。
时间复杂度：O(1)

2. 代码执行层面

仅函数调用、基础四则运算、一次打印输出，无循环、无递归、无数组遍历，全程固定常数操作，仍为 O(1)。

五、额外空间复杂度分析

程序仅开辟固定数量变量：

• 主函数：变量n、result

• minCost函数：入参n，无额外数组、切片、递归栈、动态分配内存
分配的内存空间数量不随n增大而增加，空间占用恒定不变。
额外空间复杂度：O(1)

补充总结

1. 题目看似需要动态规划/模拟拆分求最小值，实际数学证明所有拆分方案总代价完全相等，不存在“更优方案”；

2. 最优解直接使用数学公式一步算出，无需模拟拆分过程；

3. 无论n取1~500内任意数值，计算、空间开销均为常数级别。

Go完整代码如下：

package main

 import (
    "fmt"
)

 func minCost(n int)int {
    return n * (n - 1) / 2
}

 func main() {
    n := 3
    result := minCost(n)
    fmt.Println(result)
}

Python完整代码如下：

# -*-coding:utf-8-*-

 def min_cost(n: int) -> int:
    return n * (n - 1) // 2

 def main():
    n = 3
    result = min_cost(n)
    print(result)

 if __name__ == "__main__":
    main()

C++完整代码如下：

  


 int minCost(int n) {
    return n * (n - 1) / 2;
}

 int main() {
    int n = 3;
    int result = minCost(n);
    std::cout << result << std::endl;
    return 0;
}

我们相信人工智能为普通人提供了一种“增强工具”，并致力于分享全方位的AI知识。在这里，您可以找到最新的AI科普文章、工具评测、提升效率的秘籍以及行业洞察。 欢迎关注“福大大架构师每日一题”，发消息可获得面试资料，让AI助力您的未来发展。