題目來源：NYOJ90

問題描述：

　　將正整數(shù)n表示成一系列正整數(shù)之和：n=n1+n2+…+nk，?其中n1≥n2≥…≥nk≥1，k≥1。?正整數(shù)n的這種表示稱為正整數(shù)n的劃分。求正整數(shù)n的不?同劃分個(gè)數(shù)。?
　　例如正整數(shù)6有如下11種不同的劃分：?
　　　　6；?
　　　　5+1；?
　　　　4+2，4+1+1；?
　　　　3+3，3+2+1，3+1+1+1；?
　　　　2+2+2，2+2+1+1，2+1+1+1+1；?
　　　　1+1+1+1+1+1。?

輸入：

　　第一行是測試數(shù)據(jù)的數(shù)目M（1<=M<=10）。以下每行均包含一個(gè)整數(shù)n（1<=n<=10）。

輸出：

　　輸出每組測試數(shù)據(jù)有多少種分法。

分析：

　　對于整數(shù)劃分，相當(dāng)于把正整數(shù)n寫成下面形式：

　　　　n=n1+n2+…+nk （其中n≥n1≥n2≥…≥nk≥1，k≥1），則{n1, n2, ……,nk}為n的一個(gè)劃分。

　　現(xiàn)假設(shè)n1 <= m，即：{n1, n2, ……,nk}中最大的數(shù)不超過m，則稱{n1, n2, ……,nk}是n的一個(gè)m上限劃分。記n的m上限劃分為f(n,m)。因此，此題的解便是f(n,n)。對于f(n,m)，分析可得下面的遞推關(guān)系式：

　　1、當(dāng)n = 1時(shí)，f(n,m)=1。即1只有{1}這一種劃分。

　　2、當(dāng)m = 1時(shí)，f(n,m)=1。即此時(shí)只有{1, 1,……,1}（共n個(gè)1）這一種劃分。

　　3、當(dāng)m = n時(shí)，f(n,m) = f(n,n) = f(n, n-1) + 1。其中"+1"對應(yīng)的就是{n}這種劃分，其他的劃分中，必定所有數(shù)都小于n。

　　4、當(dāng)m > n時(shí)， f(n,m) = f(n,n)，因?yàn)閚的劃分中不可能存在大于n的數(shù)。

　　5、當(dāng)m < n時(shí)， f(n,m) = f(n-m, m) + f(n, m-1)。其中f(n-m,m)表示包含m的劃分，f(n,m-1)表示不包含m的劃分。

代碼：

　　根據(jù)上面的遞推式，同樣可以寫出遞歸和遞推的代碼。

　　遞歸代碼仍然存在重復(fù)計(jì)算，時(shí)間代價(jià)大。

　　遞推代碼就是計(jì)算f(1,1)到f(n,n)的過程，所以時(shí)間和空間復(fù)雜度都是O(n^2)，而且由于f(n,m)是和f(n-m,m)、f(n,m-1)，所以不太適合進(jìn)行空間復(fù)雜度的優(yōu)化。

　　代碼見github:整數(shù)劃分1

轉(zhuǎn)載于:https://www.cnblogs.com/DwyaneTalk/p/4617057.html

《新程序員》：云原生和全面數(shù)字化實(shí)踐50位技術(shù)專家共同創(chuàng)作，文字、視頻、音頻交互閱讀

總結(jié)

以上是生活随笔為你收集整理的算法笔记——整数划分1的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。