题解 | #放苹果#

public class Main{
	public static void main(String[] args) {		Scanner sc = new Scanner(System.in);
		while(sc.hasNext()){
			int m = sc.nextInt();
			int n = sc.nextInt();
			int[][] f = new int[m+1][n+1];
			/*
			 * 设f[m][n]为m个苹果，n个盘子时，有几种放法。
			 * f[m][n]分情况讨论：
			 * 一、当m<n,苹果少于盘子，则一定有空的盘子，所以f[m][n]=f[m][m];
			 * 二、当m>=n,苹果多于盘子，则可以有空的盘子，也可以没有空的盘子。
			 * （1）当没有空的盘子，则每个盘子至少有一个苹果。将这个苹果与盘子看做一个整体的新盘子，
			 * 则要求的就是将m-n个苹果放入n个盘子的情况，所以f[m][n]=f[m-n][n];
			 * （2）当有空盘子时，至少存在一个空盘子，此空盘子对于放法不会产生影响，所以f[m][n]=f[m][n-1]。
			 * 0<=m<=10;1<=n<=10;
			 * f[0][n] = 1;0个苹果放入n个盘子，只有一种放法。
			 * f[1][n] = 1;1个苹果放入n个盘子，只有一种放法。
			 * f[m][1] = 1;m个苹果放入1个盘子，只有一种放法。
			 * */
			for(int i=0;i<=m;i++){
				for(int j=1;j<=n;j++){
					if(i==0||i==1||j==1){
						f[i][j] = 1;
					}
					else{
						if(i<j){
							f[i][j] = f[i][i];
						}
						else{
							f[i][j] = f[i-j][j]+f[i][j-1];
						}
					}
					//System.out.println("m: "+i+" n: "+j+" f[m][n]: "+f[i][j]);
				}
			}
			System.out.println(f[m][n]);
		}
	}
}