信息奥赛题解｜放苹果

🚀 题目浏览

【题目描述】

把 $m$ 个同样的苹果放在 $n$ 个同样的盘子里，允许有的盘子空着不放，问共有多少种不同的分法。（$5,1,1$ 和 $1,1,5$ 是同一种方法）

【输入】

第一行是测试数据的数目 $t$，以下每行均包括二个整数 $m$ 和 $n$，以空格分开。

【输出】

对输入的每组数据 $m$ 和 $n$，用一行输出相应的结果。

【数据范围】

$1\leq m,n\leq 10$，$0 \leq t \leq 20$。

【输入样例1】

1
7 3

【输出样例1】

【输入样例2】

【输出样例2】

2
4
2

【原题链接】

https://www.luogu.com.cn/problem/P2386

☘️ 题解分析

本题可以使用的方法很多，如递归、动态规划、搜索等。详细题解可以查看洛谷的题解报告：

放苹果——洛谷题解

放苹果——B站视频讲解

🧑🏻‍💻 C++ 代码

递归法

🍉 PS：按照递归方程，推样例 s(7,3)，会出现 s(0,2)，所以 m = 0 时，也要返回 $1$；

#include<bits/stdc++.h>

using namespace std;

int s(int m, int n) {
    //没有苹果或者只有1个苹果或者只有1个盘子，均只有1个放法，是递归的出口
    if (m == 0 || m == 1 || n == 1) return 1;

    //当盘子数n > 苹果数m时，每个盘子假设放1个苹果，最多也只能放m个盘子，剩下的 n-m 个盘子始终是空的
    //所以此时 s(m,n) = s(m,m)
    if (n > m) return s(m, m);

    //当盘子数n <= 苹果数m时，分为 没有空盘子 和 至少空1个盘子 两种情况讨论
    if (n <= m) return s(m - n, n) + s(m, n - 1);
}

int main() {
    int m, n, t;

    //t组测试样例
    cin >> t;
    while (t--) {
        //读入苹果数m和盘子数n
        cin >> m >> n;
        cout << s(m, n) << endl;
    }

    return 0;
}

🤔 思考：上述递归条件的等号能不能换位置，改成 n >= m 和 n < m ?

动态规划

#include<bits/stdc++.h>

using namespace std;

const int N = 15;
int t, m, n;
int dp[N][N];

int main() {
    ios::sync_with_stdio(false);  //cin读入优化
    cin.tie(0);

    //dp[m][n]表示m个苹果放n个盘子的方案数
    for (int i = 0; i < N; ++i) {   //i代表m
        for (int j = 0; j < N; ++j) {  //j代表n
            //初始化
            if (i == 0 || i == 1 || j == 0 || j == 1)
                dp[i][j] = 1;
                //统计
            else if (j > i)
                dp[i][j] = dp[i][i];
            else
                dp[i][j] = dp[i - j][j] + dp[i][j - 1];
        }
    }

    //直接输出答案
    cin >> t;
    while (t--) {
        cin >> m >> n;
        cout << dp[m][n] << endl;
    }

    return 0;
}