华为机试题61-放苹果

描述

把m个同样的苹果放在n个同样的盘子里，允许有的盘子空着不放，问共有多少种不同的分法？

注意：如果有7个苹果和3个盘子，（5，1，1）和（1，5，1）被视为是同一种分法。

数据范围：0≤m≤10 ，1≤n≤10 。

输入描述：

输入两个int整数

输出描述：

输出结果，int型

示例1

输入：

7 3

输出：

8

---

动态规划的题对我来说都是难题，根本想不出状态转移方程要怎么写。。。

---

解题思路：

已知苹果个数为m（0~10），盘子个数为n（1~10），有两种情况：

先设f[m][n]为m个苹果，n个盘子时的分法；

1、如果苹果个数m<盘子个数n，那么肯定会有n-m个盘子是空着的，去除这些盘子也不影响苹果的分发，于是可得f[m][n]=f[m][m]；

2、如果苹果个数m≥盘子个数n，此时也有两种情况：

2.1、如果有盘子为空，则f[m][n]=f[m][n-1]；

2.2、如果没有盘子为空，即每个盘子至少放了一个苹果，那我们把这n个苹果扔了，再用剩下的苹果m-n分发，也是同样大小的分法，即f[m][n]=f[m-n][n];

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

了解以上后，用递归还是动态规划，就看个人选择了，用递归的话注意添加结束条件，否则会一直递归，然后出错。用动态规划的话，也要添加初始值，这里苹果数m为0或者1时，给定f[m][n]的初始值为1，当盘子数n=1时，f[m][n]的初始值为1，即所有苹果放这一个盘子上。

ps：我认为把所有苹果分完就算一种分法（不重复为前提），所以如果苹果个数为0，所有盘子全空，算1种分法。

以下代码用的动态规划方法：

#include <stdio.h>
#define    N        11
int main()
{
    int f[N][N],m,n,i,j;
    scanf("%d%d",&m,&n);
    for(i=0;i<N;i++)        //i为苹果个数
    {
        for(j=1;j<N;j++)    //j为盘子个数
        {
            if(i==0||i==1)        //0个或1个苹果时，为1种分法
                f[i][j]=1;
            else
            {
                if(j==1)          //只有1个盘子时，也是1种分法
                    f[i][j]=1;
                else
                {
                    if(i<j)
                        f[i][j]=f[i][i];    //盘子数更多，把肯定空的盘子去了，分法保持不变
                    else
                        f[i][j]=f[i][j-1]+f[i-j][j];
                }  
            }
        }
    }
    printf("%d\n",f[m][n]);
    return 0;
}