前置文章：递归算法：www.jianshu.com/p/703069f3ba3f .
在说到递归算法的时候，逃不开的一个经典问题是整数划分问题。整数划分，试讲一个正整数n表示成多个正整数的和：n=m1+m2+……+mk( mk为正整数，且 1 <= mk <=n )，那么{ m1,m2……mk } 就是n的一个划分。
那么整数划分是什么意思呢？打个比方，我家里现在还是有那一片苹果林，我这去年就不养兔子了，吃穷了，养不起。这样今年结的苹果我可以拿来送人或者是拿去卖了。正好最近我家里要来一些我的老同学，我现在不知道来多少人，只知道最少来两个，最多四个人，恰巧我这苹果林结的苹果有四斤熟了，我就打算送给他们。但是我这不确定来多少人，我就要提前规划好我这四斤苹果怎么送：
我这里来俩人，这俩人跟我关系不一样，一个关系好一个关系差，那我就给那关系好的三斤，剩下一斤给另一个：3+1；来这俩人跟我关系一样呢，那我就一人两斤：2+2；
我这里来三人，我就根据关系分了，一人两斤，剩下俩人一人一斤：2+1+1；
要是来四人，正好一人一斤，不偏不倚：1+1+1+1。
我给这四斤苹果做的这个划分，就是一个整数划分。在整数划分里面，一个整数的划分种最大家数s不超过m，即s=max（m1,m2……,mk)<= m,这个划分就叫做n的一个m划分，记做 f (n,m)。划分问题现在就转换成了求n的划分个数f (n,n)。
建立f (n,m)的划分关系：
(1) f(1,m) = 1,m>=1; n =1，划分只有一种，就是1.
(2) f(n,1) = 1,n>=1; m =1，划分只有一种，n个1.
(3) f(n,m) = f(n,n);最大加数不能超过n.
(4) f(n,n) = f(n,n-1); n的划分是由s=n划分和s<=n-1的划分构成。也就是1+3 = 1+1+2
(5) f(n,m) = f(n,m-1) + f(n-m,m) n>m>1;也就是最大加数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
然后做出正整数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);
}
这个样子，无论是整数划分问题还是我的苹果划分问题都解决了，那我接下来就只需要等着我那些老同学来，然后分四斤苹果了，至于苹果林结的剩下的40斤苹果，我去问问我家喵主子吃不吃。
网友评论