把M个同样的苹果放在N个同样的盘子里，允许有的盘子空着不放，问共有多少种不同的分法（用K表示）？请设计一个算法计算K值（只需要计算K值，不用把具体的分法输出）。注意：5，1，1和1，5，1是同一种分法。
正确答案:
例：M=7，N=3则有K=8
可能的分法为：
7，0，0
6，1，0
5，2，0
4，3，0
5，1，1
4，2，1
3，3，1
3，2，2
设f（m，n）为m个苹果，n个盘子的放法数目，则先对n作讨论，如果n>m，必定有n-m个盘子永远空着，去掉它们对摆放苹果方法数目不产生影响；即if（n>m）f（m，n）=f（m，m）当n<=m时，不同的放法可以分成两类：即有至少一个盘子空着或者所有盘子都有苹果，前一种情况相当于f（m，n）=f（m，n-1）；后一种情况可以从每个盘子中拿掉一个苹果，不影响不同放法的数目，即f（m，n）=f（m-n，n）.而总的放苹果的放法数目等于两者的和，即f（m，n）=f（m，n-1）+f（m-n，n）。边界条件为m=0或n=1时，只有一种放法。
可能的分法为：
7，0，0
6，1，0
5，2，0
4，3，0
5，1，1
4，2，1
3，3，1
3，2，2
设f（m，n）为m个苹果，n个盘子的放法数目，则先对n作讨论，如果n>m，必定有n-m个盘子永远空着，去掉它们对摆放苹果方法数目不产生影响；即if（n>m）f（m，n）=f（m，m）当n<=m时，不同的放法可以分成两类：即有至少一个盘子空着或者所有盘子都有苹果，前一种情况相当于f（m，n）=f（m，n-1）；后一种情况可以从每个盘子中拿掉一个苹果，不影响不同放法的数目，即f（m，n）=f（m-n，n）.而总的放苹果的放法数目等于两者的和，即f（m，n）=f（m，n-1）+f（m-n，n）。边界条件为m=0或n=1时，只有一种放法。
答案解析:有
微信扫一扫手机做题