🔗 🟡 3857. Minimum Cost to Split into Ones

Problem Statement

題目簡述

給定一個整數 $n$ 。
每次操作可以將一個整數 $x$ 拆分為兩個正整數 $a$ 和 $b$ （滿足 $a+b=x$ ），其代價為 $a \times b$ 。
求將 $n$ 拆分為 $n$ 個 $1$ 的最小總代價。

Constraints

約束條件

$1 \le n \le 500$

思路：等價轉化與不變量

不變量

這道題目乍看之下是經典的區間 DP / 記憶化搜索，以本題的數據而言也確實可以用這種方法通過本題。但多輸出幾組小數據就會發現：對於同一個 $n$ ，所有拆分方式的總代價竟然都一樣！ 這暗示總代價可能是個不變量——因此關鍵不在於怎麼拆最省，而在於每次操作消耗的「資源」到底是什麼。

方法一：記憶化搜索（直覺做法）

先不管結論，從最直覺的暴力思路出發。

將 $n$ 拆成 $x$ 和 $n-x$ 兩部分，當次代價為 $x \times (n-x)$ ，再加上各自繼續拆分的最小代價。利用對稱性，只需枚舉 $x$ 從 $1$ 到 $\lfloor \frac{n}{2} \rfloor$ 。

常見誤區

為什麼只枚舉到 $\lfloor n/2 \rfloor$ 而非 $n-1$ ？因為 $(x, n-x)$ 和 $(n-x, x)$ 是同一種拆分，對稱性讓我們只需檢查一半。

狀態轉移式：

dfs(n) = \min_{1 \le x \le \lfloor \frac{n}{2} \rfloor} \big( dfs(x) + dfs(n-x) + x \cdot (n-x) \big)

遞迴邊界： $n=1$ 時無法再拆分，代價為 $0$ 。

複雜度分析

時間複雜度： $\mathcal{O}(n^2)$ ， $n$ 個狀態，每個狀態枚舉約 $n/2$ 次。
空間複雜度： $\mathcal{O}(n)$ ，遞迴深度與記憶化陣列均為 $O(n)$ 。

方法二：完全圖斷邊模型（等價轉化）

DP 過了，但你多跑幾組數據就會發現不對勁——每一種拆分方式的總代價居然完全相同。這不是巧合，而是 $a \times b$ 這個算式藏著另一層意思，只是被「拆分」的包裝蓋住了。

重新詮釋代價

把一次拆分 $(x \to a, b)$ 想像成：將大小為 $x$ 的點集切成左右兩組，左組 $a$ 個點、右組 $b$ 個點。左組每個點與右組每個點之間都有一條連邊，總共恰好 $a \times b$ 條。拆分代價 = 這次操作切斷的邊數。

換句話說，整個問題可以放進一張完全圖裡理解：

初始： $n$ 個節點兩兩相連（完全圖），總邊數 $C(n,2) = \frac{n(n-1)}{2}$ 。
一次拆分：把當前某個點集一分為二，等價於切斷兩組之間的所有連邊。被切斷的邊數恰好是兩個子集大小的乘積。
遞迴終止：持續劃分，直到每個點集都只剩一個點——此時整張圖的邊已全部被切斷。

關鍵在於：兩點一旦被分到不同集合，就再也不會回到同一集合，所以每條邊在整個過程中只會被切斷一次。最終所有邊都必須切斷。

結論

無論拆分順序如何，被切斷的總邊數恆為初始完全圖的總邊數。答案就是 $\frac{n(n-1)}{2}$ 。

複雜度分析

時間複雜度： $\mathcal{O}(1)$ 。
空間複雜度： $\mathcal{O}(1)$ 。

Code

方法一：記憶化搜索 (Memoization)

@cache
def dfs(n: int) -> int:
    if n == 1:
        return 0
    res = float("inf")
    for x in range(1, n // 2 + 1):
        res = min(res, dfs(x) + dfs(n - x) + x * (n - x))
    return res

class Solution:
    def minCost(self, n: int) -> int:
        return dfs(n)

方法二：數學推導（完全圖斷邊模型）

1
2
3

class Solution:
    def minCost(self, n: int) -> int:
        return n * (n - 1) // 2