题目描述：
输入m,n，分别表示苹果数与盘子的总数，要求输出苹果放在n个盘子的方法总数（注意511和151是一种情况），例如输入 7 3 输出8（（7），（6,1），（5,2），（4,3），（5,1,1），（4,2,1），（3,3,1），（3,2,2））
思路：
最典型的解法整数分解，例如给定n个苹果，把苹果放到k个盘子里，允许有的盘子为空，不妨设 f（n , k ) (边缘条件为当 n = 0 ，1时，返回1，当 k = 1 时，返回1）表示结果，分析一下可以知道有两种放的方法，一种是有空盘，一种是没空盘。
没空盘的情况可以知道每个盘子里至少有一个苹果，也就是说这种情况的总数为 f ( n-k , k ) 。
而有空盘的情况，我们可以假设最后一个盘子为空，则这种情况的总数为f ( n , k-1 ) (无需考虑多个盘子为空的情况，递归时必然会出现）
所以状态转移方程为 f ( n , k ) = f ( n-k , k ) + f ( n , k-1 )
import java.util.Scanner; /**
* 把M个同样的苹果放在N个同样的盘子里，允许有的盘子空着不放，
* 问共有多少种不同的分法？（用K表示）5，1，1和1，5，1 是同一种分法。
*/
public class PlayApples { public static void main(String[] args) {
//输入读取参数
Scanner cin = new Scanner(System.in) ;
int apples = cin.nextInt() ;
int planes = cin.nextInt() ;
cin.close(); System.out.println(count(apples,planes)) ; } /**
* 最典型的整数分解
* 例如给定n个苹果，把苹果放到k个盘子里，允许有的盘子为空， 不妨设 f（m , n )
* (边缘条件为当 m == 0 ，1时，返回1，当 n == 1 时，返回1）表示结果，
* 分析一下可以知道有两中放的方法，一种是有空盘，一种是没空盘，
* 没空盘的情况可以知道每个盘子里至少有一个苹果，也就是说这种情况的总数为 f ( n-k , k ) 。
* 而有空盘的情况，我们可以假设最后一个盘子为空，则这种情况的总数为f ( n , k-1 ) (无需考虑多个盘子为空的情况，递归时必然会出现）
* 所以状态转移方程为 f ( n , k ) = f ( n-k , k ) + f ( n , k-1 )。
*
* 而如果是不允许有空盘子的情况，则可以由上面的情况推出，
* 设 d ( n , k ) 表示把n个苹果放到k个盘子里，不允许有空盘子的方法总数，
* 则有f ( n , k ) = Σ ( 1 <= i <= k ) d ( n , i )
* 所以 d ( n , k ) = f ( n , k ) - f ( n , k-1 )
*
* @param m 苹果数量
* @param n 盘子数量
* @return
*/
private static int count(int m, int n) {
//n为0 是错误的，故返回0
if(n == 0){
return 0 ;
}
//m == 0,1时和 n == 1时均只有一种放法
if(m == 0 || n == 1 || m == 1 ){
return 1 ;
}else if(m < 0){
//m < 0 时，也是错误的情形，所以返回0
return 0 ;
}else{
//递归调用
return count(m-n,n) + count(m,n-1) ;
}
}
}
Code
扩展：
而如果是不允许有空盘子的情况，则可以由上面的情况推出，设 d ( n , k ) 表示把n个苹果放到k个盘子里，不允许有空盘子的方法总数，则有
f ( n , k ) = Σ ( 1 <= i <= k ) d ( n , i ) 所以 d ( n , k ) = f ( n , k ) - f ( n , k-1 )