把M个同样的苹果放在N个同样的盘子里，允许有的盘子空着不放，问共有多少种不同的分法？（用K表示）5，1，1和1，5，1 是同一种分法。

第一行是测试数据的数目t（0 <= t <= 20）。以下每行均包含二个整数M和N，以空格分开。1<=M，N<=10。

对输入的每组数据M和N，用一行输出相应的K。



二、题解

        这道题最重要的就是要找到突破口，这个突破口就是把所有的结果分为，有一个盘子为空和全部盘子都有苹果这两种情况。之后再递归求解子问题。

        f(m-n,n)：每个盘子都有苹果

则，f[m][n] = f[m-n][n]+f[m][n-1]

        这里有详细题解和扩展http://www.cnblogs.com/celia01/archive/2012/02/19/2358673.html

三、Java代码

 

import java.util.Scanner; 

public class Main {

	public static int f(int a,int b){

		if(a<0)

			return 0;

		if(a==0||b==1)

			return 1;

		return f(a-b,b)+f(a,b-1);

	}

    public static void main(String[] args) {

       Scanner cin = new Scanner(System.in);

       int n=cin.nextInt();

       int a,b;

       for(int i=0;i<n;i++){

    	   a=cin.nextInt();

    	   b=cin.nextInt();

    	   System.out.println(f(a,b));

       }

    }

  }

版权声明：本文为博主原创文章，未经博主允许不得转载。