[编程题]放苹果

╰半橙微兮° 2022-09-30 12:53 191阅读 0赞

> Talk is cheap, show me the code.

### 一、问题描述 ###

把M个同样的苹果放在N个同样的盘子里，允许有的盘子空着不放，问共有多少种不同的分法？（用K表示）5，1，1和1，5，1 是同一种分法。

输入：每个用例包含二个整数M和N。0<=m<=10，1<=n<=10。

**输入描述：**

输入两个int整数

**输出描述：**

输出结果，int型

**输入例子：**

7 3

**输出例子：**

### 二、解题思路 ###

1.第一种解法，利用动态规划的思想来解决。把 m 个苹果放进 n 个盘子里，分别考虑 min(m, n) 个子问题，即把 m 个苹果放进 i 个盘子里，这里 1 <= i <= min(m,n)，注意这里放进去表示每个盘子里不能为空，那么就可以等同考虑为每个盘子里都放了一个苹果，即问题转化为需要把 m-i 个苹果放进 i 个盘子里，那么 dp\[m, n\] = dp\[m-1,1\]+…+dp\[m-min(m,n),min(m,n)\]，只是这里要注意特殊情况，当 dp\[m-i, i\] 为零时其实方法是为 1 的而不是 0。初始化时dp\[0\]\[i\] = 0, dp\[i\]\[1\] = 1。

代码：

#include <iostream>
    using namespace std;
    
    int putApple(int m, int n)
    {
        int num = 0;
        int **dp = new int*[m+1];
        for(int i = 0; i < m+1; i++)
        {
            dp[i] = new int[n];
        }
        for(int i = 0; i < n; i++)
            dp[0][i] = 0;
        for(int i = 1; i < m+1; i++)
            dp[i][0] = 1;
        for(int i = 1; i < m+1; i++)
        {
            for(int j = 1; j < n; j++)
            {
                int sum = 0;
                for(int k = 1; k <= min(j+1, i); k++)
                {
                    sum += dp[i-k][k-1];
                    if(dp[i-k][k-1] == 0)
                        sum += 1;
                }
                dp[i][j] = sum;
            }
        }
        num = dp[m][n-1];
    
        for(int i = 0; i < m+1; i++)
        {
            delete dp[i];
            dp[i] = 0;
        }
        delete [] dp;
        dp = 0;
        return num;
    }
    
    void test1()
    {
        int m, n;
        while(cin >> m >> n)
        {
            cout << putApple(m, n) << endl;
        }
    }
    
    int main()
    {
        test1();
        return 0;
    }

2.第二种解法，采用递归的思路。将 m 个苹果放入 n 个盘子里，分两种情况考虑，第一种情况是当必须至少有一个盘子空着，此时f(m, n) = f(m, n-1)，这种情况下当 m < n 时显然成立 第二种情况是当每个盘子里面必须至少要放一个苹果，这种情况要求 m >= n，此时 f(m, n) = f(m-n, n)，特殊情况如果 m == n 时， f(m, n) = 1。初始化时 dp\[m\]\[1\] = 1;

代码：

#include <iostream>
    using namespace std;
    
    int putApple(int m, int n)
    {
        if(n == 1)
            return 1;
        if(m == 0)
            return 0;
        if(m < n)
            return putApple(m, n-1);
        else if(m == n){
            return 1+putApple(m, n-1);
        } else {
            return putApple(m-n, n)+putApple(m, n-1);
        }
    }
    
    void test1()
    {
        int m, n;
        while(cin >> m >> n)
        {
            cout << putApple(m, n) << endl;
        }
    }
    
    int main()
    {
        test1();
        return 0;
    }