??????? 前置文章：遞歸算法：www.itdecent.cn/p/703069f3ba3f .
??????? 在說(shuō)到遞歸算法的時(shí)候，逃不開(kāi)的一個(gè)經(jīng)典問(wèn)題是整數(shù)劃分問(wèn)題。整數(shù)劃分，試講一個(gè)正整數(shù)n表示成多個(gè)正整數(shù)的和：n=m1+m2+……+mk( mk為正整數(shù)，且 1 <= mk <=n )，那么{ m1,m2……mk } 就是n的一個(gè)劃分。
??????? 那么整數(shù)劃分是什么意思呢？打個(gè)比方，我家里現(xiàn)在還是有那一片蘋(píng)果林，我這去年就不養(yǎng)兔子了，吃窮了，養(yǎng)不起。這樣今年結(jié)的蘋(píng)果我可以拿來(lái)送人或者是拿去賣了。正好最近我家里要來(lái)一些我的老同學(xué)，我現(xiàn)在不知道來(lái)多少人，只知道最少來(lái)兩個(gè)，最多四個(gè)人，恰巧我這蘋(píng)果林結(jié)的蘋(píng)果有四斤熟了，我就打算送給他們。但是我這不確定來(lái)多少人，我就要提前規(guī)劃好我這四斤蘋(píng)果怎么送：
??????????? 我這里來(lái)倆人，這倆人跟我關(guān)系不一樣，一個(gè)關(guān)系好一個(gè)關(guān)系差，那我就給那關(guān)系好的三斤，剩下一斤給另一個(gè)：3+1；來(lái)這倆人跟我關(guān)系一樣呢，那我就一人兩斤：2+2；
??????????? 我這里來(lái)三人，我就根據(jù)關(guān)系分了，一人兩斤，剩下倆人一人一斤：2+1+1；
??????????? 要是來(lái)四人，正好一人一斤，不偏不倚：1+1+1+1。
??????? 我給這四斤蘋(píng)果做的這個(gè)劃分，就是一個(gè)整數(shù)劃分。在整數(shù)劃分里面，一個(gè)整數(shù)的劃分種最大家數(shù)s不超過(guò)m，即s=max（m1,m2……,mk)<= m,這個(gè)劃分就叫做n的一個(gè)m劃分，記做 f (n,m)。劃分問(wèn)題現(xiàn)在就轉(zhuǎn)換成了求n的劃分個(gè)數(shù)f (n,n)。
??????? 建立f (n,m)的劃分關(guān)系：
??????????? (1) f(1,m) = 1,m>=1;? n =1，劃分只有一種，就是1.
??????????? (2) f(n,1) = 1,n>=1; m =1，劃分只有一種，n個(gè)1.
??????????? (3) f(n,m) = f(n,n);最大加數(shù)不能超過(guò)n.
??????????? (4) f(n,n) = f(n,n-1); n的劃分是由s=n劃分和s<=n-1的劃分構(gòu)成。也就是1+3 = 1+1+2
??????????? (5) f(n,m) = f(n,m-1) + f(n-m,m) n>m>1;也就是最大加數(shù)s不大于m的劃分，是由s=m的劃分和s<=m-1的劃分組成。
??????? 這樣，就能做出f(n,m) 的遞歸公式：
???????????????????????????? 1?????????????????????????????????? n=1,m=1
??????????? f(n,m) =??? f(n,n)??????????????????????????? n<m
???????????????????????????? 1+f(n,n-1)???????????????????? n=m
???????????????????????????? f(n,m-1）+ f(n-m,m)??? n>m>1
??????? 然后做出正整數(shù)n的劃分:
int split ( int n, int m ) {
??????? if ( n==1 || m==1 ) return 1;
??????? else if (n < m ) return split(n,n);
??????? else if (n==m) return split(n,n-1)+1 ;
??????? else return split(n,m-1) + split(n-m,m);
}
??????? 這個(gè)樣子，無(wú)論是整數(shù)劃分問(wèn)題還是我的蘋(píng)果劃分問(wèn)題都解決了，那我接下來(lái)就只需要等著我那些老同學(xué)來(lái)，然后分四斤蘋(píng)果了，至于蘋(píng)果林結(jié)的剩下的40斤蘋(píng)果，我去問(wèn)問(wèn)我家喵主子吃不吃。
?
