📘 題目敘述
給你一個整數 n。一次操作中，你可以把整數
x 拆成兩個正整數 a 和 b，使得
a + b = x，花費是 a * b。請回傳把
n 拆成 n 個 1 的最小總花費。
條件限制
1 <= n <= 500
🧠 解題思路
我用遞迴拆分去累積花費：每次把 k 拆成
a = k/2 與 b = k-a，加上
a*b 後繼續拆。核心觀察是無論怎麼拆，總花費都會固定是
n*(n-1)/2，因為每一對不同的
1 只會在某一次被分開，且只計一次。
所有變數
cost：累積總花費-
split(k)：把k拆到全是 1 的遞迴函式 a、b：本次拆分的兩部分
🪜 主要流程步驟
1. 遞迴終止條件
k == 1 時直接回傳。
2. 決定拆分
令 a = k/2、b = k-a。
3. 累加成本
把 a*b 加到 cost。
4. 繼續拆左右兩邊
呼叫 split(a) 與 split(b)。
5. 主函式回傳
minCost(n) 回傳 cost。
⏱️ 複雜度
- 時間複雜度：
O(n) - 空間複雜度：
O(log n)
💻 程式碼實作
class Solution {
public:
int cost = 0;
void split(int k) {
if (k == 1) {
return;
}
int a = k / 2;
int b = k - a;
cost += a * b;
split(a);
split(b);
}
int minCost(int n) {
split(n);
return cost;
}
};🔗 題目連結
https://leetcode.com/contest/weekly-contest-491/problems/minimum-cost-to-split-into-ones/