放苹果问题

题目描述：

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

输入
每个用例包含二个整数M和N。0<=m<=10，1<=n<=10。

样例输入
7 3
样例输出
8

思路：m个苹果放到n个盘子,可以拆分问题为有盘子不放苹果，和每个盘子都放苹果
开始想到有盘子不放苹果：即分为有1个，2个，3个...n-1个盘子不放的情况，却产生了重复的数据。
这里只需要记录有一个不放的情况dp[m,n-1],在下轮计算中，会有此基础的dp[m,n-2],即初始问题对应的两个盘子不放的情况；
递推公式：
dp[m,n]=dp[m-n,n]+dp[m,n-1]
dp[m-n,n]即先把每个蓝子都放置一个，达到每个都有的效果，再把剩余的m-n个分到n个篮子

import java.util.Scanner;
public class Main{
    public static void main(String[] args){
        Scanner scan=new Scanner(System.in);
        while(scan.hasNext()){
            System.out.println(fun(scan.nextInt(),scan.nextInt()));
        }
    }
    public static int fun(int m,int n){
        if(m<0||n<0)
            return 0;
        if(m==1||n==1)
            return 1;
        return fun(m-n,n)+fun(m,n-1);
    }
}