华为机试题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;
}