来一个和大佬们思路不太一样的解法，希望能起到启发思路的作用。也欢迎各路朋友讨论和指正

题目中规定'1 5 1' 和'5 1 1'是同样的组合，那么对于m个苹果和n个盘子，记xix_i是第ii个盘子中的苹果数,可以认为满足非升序（或非降序）排列

m≥x1≥x2≥⋯≥xn≥0m\ge x_1 \ge x_2 \ge \cdots \ge x_n \ge 0
∑i=1nxi=m\sum_{i=1}^{n}x_i = m

我们将问题理解成（m）个苹果、（n）个盘子和最大数值为（x0=mx_0=m）的一个问题，记为f(x0,m,n)f(x_0,m,n)

那么此时往第一个盘子中摆放苹果的个数为kk个

x1=kx_1 = k

则约束表达式变为

min⁡(k,m−k)≥x2≥⋯≥xn≥0 \min(k,m-k) \ge x_2 \ge \cdots \ge x_n \ge 0
∑i=2nxi=m−k\sum_{i=2}^{n}x_i = m - k

问题就变成了（m−x1m-x_1）个苹果、（n-1）个盘子和上一个盘子内的苹果数为（x1x_1）的问题，记为 f(x1,m−x1,n−1)f(x_1,m-x_1,n-1)

更为一般性，我们记上一个盘子苹果数为xlastx_{last} , 当前剩余苹果数为mleftm_{left}，当前盘子数为nleftn_{left}. 此时问题记为f(xlast,mleft,nleft)f(x_{last},m_{left},n_{left})

只要不是只剩下一个盘子，当前问题的第一个盘子里，尝试放置从min⁡(xlast,mleft)\min(x_{last},m_{left})~~0个苹果，将其结果归结为子问题的求和

f(xlast,mleft,nleft)=∑xnow=0min⁡(xlast,mleft)f(xnow,mleft−xnow,nleft−1)f(x_{last},m_{left},n_{left}) = \sum_{x_{now}=0}^{\min(x_{last},m_{left})}f(x_{now},m_{left}-x_{now},n_{left}-1)

经过不断的嵌套之后，问题总归会来到最后一个盘子n = 1的情形，此时剩下的苹果全部放入最后的盘子，只需要满足降序排列条件即可视为存在该排列，不满足降序要求则认为是重复排列。 约束问题变为

f(xn−1,mleft,n=1)={1,mleft<=xn−10,mleft>xn−1f(x_{n-1},m_{left},n=1) = \begin{cases} &1, &m_{left} <= x_{n-1}\\ &0, &m_{left} > x_{n-1} \end{cases}

递归的程序设计如下所示，调用过程需注意初始化为f(m,m,n)f(m,m,n)

#include<stdio.h>

int Partition(int xlast,int mleft,int nleft)
{
    int x_now;
    int cnt = 0;
    int tmp;
    if(nleft == 1)
    {
        if(mleft > xlast) // 不满足降序
            return 0;
        else 
            return 1;
    }        
    for(x_now = (mleft>xlast?xlast:mleft); x_now >= 0; x_now--) // min(mleft, xlast)
    										// (mleft>xlast?xlast:mleft)
    {
        tmp = Partition(x_now, mleft - x_now, nleft - 1);
        if(tmp)
            cnt+=tmp;
        else // 减少部分不必要的计算
            break;
    }    
    return cnt;
}

int main()
{
    int m,n ;
    int cnt = 0;
    while(scanf("%d %d",&m,&n)!=EOF)
    {
        cnt = Partition(m,m,n);
    }
    printf("%d",cnt);
    return 0;
}