题目链接：
关于放苹果的那些事。。。。。。。。。。
今天偶然看到一个关于整数划分的算法， 仔细看了后，我想到了放苹果的事，其实这个问题困扰了我很久，一直没想明白放苹果的原理。记得当时做这个题的时候，自己的分析的方法和整数划分的算法是一样的，就是没想到用递归就能做出来，看了一位dn的博客，终于明白是怎么回事了.........
例子，
整数划分的思想如下： 整数划分问题是将一个正整数n拆成一组数连加并等于n的形式，且这组数中的最大加数不大于n。 如6的整数划分为 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 共11种。下面介绍一种通过递归方法得到一个正整数的划分数。 递归函数的声明为 int split( int n, int m) ; 其中n为要划分的正整数，m是划分中的最大加数(当m > n时，最大加数为n)， 1 当n = 1或m = 1时，split的值为1，可根据上例看出，只有一个划分1 或 1 + 1 + 1 + 1 + 1 + 1 可用程序表示为if(n == 1 || m == 1 ) return 1 ; 2 下面看一看m 和 n的关系。它们有三种关系 ( 1 ) m > n 在整数划分中实际上最大加数不能大于n，因此在这种情况可以等价为split(n, n) ; 可用程序表示为if(m > n) return split(n, n) ; ( 2 ) m = n 这种情况可用递归表示为split(n, m - 1 ) + 1 ，从以上例子中可以看出，就是最大加 数为6和小于6的划分之和 用程序表示为if(m == n) return (split(n, m - 1 ) + 1 ) ; ( 3 ) m < n 这是最一般的情况，在划分的大多数时都是这种情况。 从上例可以看出，设m = 4 ，那split( 6 , 4 )的值是最大加数小于4划分数和整数2的划分数的和。 即 split( 6 , 4 ) = split( 6 , 3 ) + split( 2 , 4 ) 因此，split(n, m)可表示为split(n, m - 1 ) + split(n - m, m) 按照整数划分的思想，将一个整数划分为若干(x<=n) 整数，按由大到小逐级递减的顺序排列, 这样保证了不会出现 5，1，1 和 1，5，1 这种想同的情况，根据这样的思路来建立一个递推关系。
以前用dfs写的代码 #include " iostream " using namespace std ; int count= 0 ; int M,m,n ; void DFS( int k, int s, int t){ if( s==n ){ if(t==m) count++ ; return ; } int i ; for(i=k ; i>=0; i--){ if( t + i <= m ) { DFS(i, s+ 1 , t+i) ; } else { continue ; } }} int main(){ int i ; scanf( " %d " ,&M) ; while(M--) { count= 0 ; scanf( " %d %d " ,&m, &n) ; for(i=m ; i>=0;i--) { DFS(i, 1 ,i) ; } printf( " %d\n " ,count) ; } return 0 ; #include " iostream " using namespace std ; int split( int n, int m){ if(n==1 ||m== 1 ) return 1 ; else { if(m>n) { return split(n , n) ; } if(m==n) return split(n ,m- 1 )+ 1 ; if(m<n) { return split(n , m- 1 )+split(n-m , m) ; } }} int main(){ int t,m,n ; cin>>t ; while(t--) { cin>>m>>n ; cout<<split(m , n)<<endl ; ; } return 0 ; }