整數劃分演算法的基本資訊

整數的分割槽是將其寫為正整數之和的一種方式。例如，數字 5 的分割槽是：

• 五
• 4 + 1
• 3 + 2
• 2 + 2 + 1
• 2 + 1 + 1 + 1
• 1 + 1 + 1 + 1 + 1

請注意，更改 summands 的順序不會建立不同的分割槽。

分割槽函式本質上是遞迴的，因為較小數字的結果在較大數字的結果中顯示為分量。設 p(n, m) 為僅使用小於或等於 m 的正整數的 n 的分割槽數。可以看出，對於 m > n ， p(n) = p(n, n) ，並且 p(n, m) = p(n, n) = p(n) 。 ** ** ** ** ** ** ** **

整數分割槽演算法示例：

https://i.stack.imgur.com/5kiXt.jpg

輔助空間： O(n^2)
時間複雜度： O(n(logn))