题目：有m个苹果，n个盘子，每个盘子都可以放无数个苹果，问有多少种分法？例如有5个苹果，5个盘子，则由（11111)，（1112），（113），（14），（212），（23），（5）共7种分法。
分析：
这道题我有两种解法，一种是回溯法，即设定一个列表[1,2,…m]，然后对列表内的元素进行组合，组合条件有两个，1），它们的和为m。2），它们的个数不能超过n。当满足这种条件时，停止回溯，并记录结果。最后看这样的组合有多少个就行了。
另外一种是动态规划法，这是我这篇文章要写的解法。
因为m和n比较容易混淆谁是苹果谁是盘子，因此这里用apples代表苹果，用plates代表盘子。设f(apples,plates)函数代表当有apples个苹果，plates个盘子时的分法。
1、当apples只有1个或者0个时，那不管盘子有多少个，那只有1种分法，即只在1个盘子里放苹果，其他盘子都空着；
2、当plates只有1个时，那也只有1种分法，即把所有的苹果都放在这个盘子里；
因此，我们可以得出，
if apples <=1 or plates == 1:
f(apples,plates) = 1
3、当plates > apples时，盘子比苹果还多，那把多余的盘子撤了也不影响结果，
因此，我们可以得出，
if plates > apples：
f(apples,plates) = f(apples,apples)
4、当plates <= apples时，那可以分成两种情况：a，没有空盘子，即每个盘子上都放有苹果；b,有空盘子，即至少有1个盘子里没放苹果。
设f(apples,plates)_a代表a情况下的分法， f(apples,plates)_b代表b情况下的分法，我们可以得出，
f(apples,plates) = f(apples,plates)_a + f(apples,plates)_b
对于没有空盘子的情况，那我们可以给每个盘子上都放1个苹果，然后把剩余的苹果再分到这些盘子里。即f(apples,plates)_a = f(apples-plates,plates)
而对于有空盘子的情况，因为苹果数量不变，而盘子数量会变少，即有1个空盘子，有2个空盘子，有3个空盘子，…有plates-1空盘子，因此我们可以知道：
即f(apples,plates)_b = f(apples,plates-1)+f(apples,plates-2)+f(apples,plates-3)+…+f(apples,1)
那么，f(apples,plates-1)怎么算呢？那么此时我们就又回到了第4步的起始位置，按照第4步的逻辑，再推导一遍可知：f(apples,plates-1) = f(apples,plates-1)_a + f(apples,plates-1)_b
f(apples,plates-1)_a = f(apples-(plates-1),plates-1)
f(apples,plates-1)_b = f(apples,plates-2)+f(apples,plates-3)+f(apples,plates-4)+…+f(apples,1)
观察一下f(apples,plates)_b与f(apples,plates-1)_b的结果可以知道，f(apples,plates-2)+f(apples,plates-3)+f(apples,plates-4)+…+f(apples,1)被算了两遍，因此可以得出一个重要的结论：只有1个空盘子的情况的分法里，已经包含了有2个空盘子、有3个空盘子…有plates-1个空盘子的情况。
因此，综上，可以得出当plates<=apples时， f(apples,plates) = f(apples-plates,plates) + f(appels,plates-1)
将上述四种情况用代码实现如下（引入了字典备忘录，以加快运行速率）：
devide_dict = {}def devide_apple(apples,plates):if apples <= 1 or plates == 1:return 1if plates > apples:plates = applesreturn devide_apple(apples,plates)if (apples,plates) in devide_dict:return devide_dict[(apples,plates)]else:count = devide_apple(apples-plates,plates)+devide_apple(apples, plates-1)devide_dict[(apples,plates)] = countreturn count
