题目链接

HIGH20 放苹果

题目描述

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

输入描述: 多组测试数据，每组数据占一行，包含两个整数 和 ()。

输出描述: 对每组输入，输出一个整数 ，代表分法总数。

关于模数: 题目中有一句关于取模的描述，但根据数据范围和示例，本题实际不需要取模。

解题思路

这是一个经典的整数划分问题。我们可以定义一个函数 表示将 个苹果放入 个盘子的方法数，并使用动态规划求解。

递推关系可以根据盘子的情况进行划分：

  1. 当盘子数 大于苹果数 时 ()： 此时，至少有 个盘子是空的。因为盘子是完全相同的，空盘子之间没有区别，所以这等价于将 个苹果放入 个盘子。 即 。

  2. 当盘子数 小于等于苹果数 时 ()： 这种情况可以分为两个互斥的子集：

    • 至少有一个盘子为空：如果我们确定至少留一个盘子是空的，那么问题就变成了将 个苹果放入 个盘子中，方法数为 。
    • 所有盘子都不为空：这意味着每个盘子都至少有一个苹果。我们可以先从每个盘子中拿走一个苹果，那么我们就剩下 个苹果，需要将它们再放入 个盘子中（此时盘子允许为空）。这种情况的方法数为 。

    因此，递推公式为：。

边界条件:

  • ：只有一个盘子，所有苹果只能放进去，只有一种方法。
  • ：没有苹果，所有盘子都为空，只有一种方法。

实现： 我们可以用一个二维数组 dp[N+1][M+1] 来存储计算结果，避免重复计算。

代码

#include <iostream>
#include <vector>

using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    vector<vector<int>> dp(11, vector<int>(11, 0));

    for (int i = 0; i <= 10; ++i) {
        for (int j = 1; j <= 10; ++j) {
            if (i == 0 || j == 1) {
                dp[i][j] = 1;
            } else if (i < j) {
                dp[i][j] = dp[i][i];
            } else {
                dp[i][j] = dp[i][j - 1] + dp[i - j][j];
            }
        }
    }

    int n, m;
    while (cin >> n >> m) {
        cout << dp[n][m] << endl;
    }

    return 0;
}

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int[][] dp = new int[11][11];

        for (int i = 0; i <= 10; i++) {
            for (int j = 1; j <= 10; j++) {
                if (i == 0 || j == 1) {
                    dp[i][j] = 1;
                } else if (i < j) {
                    dp[i][j] = dp[i][i];
                } else {
                    dp[i][j] = dp[i][j - 1] + dp[i - j][j];
                }
            }
        }

        while (sc.hasNextInt()) {
            int n = sc.nextInt();
            int m = sc.nextInt();
            System.out.println(dp[n][m]);
        }
        sc.close();
    }
}

dp = [[0] * 11 for _ in range(11)]

for i in range(11):
    for j in range(1, 11):
        if i == 0 or j == 1:
            dp[i][j] = 1
        elif i < j:
            dp[i][j] = dp[i][i]
        else:
            dp[i][j] = dp[i][j-1] + dp[i-j][j]

try:
    while True:
        line = input()
        if not line:
            break
        n, m = map(int, line.split())
        print(dp[n][m])
except EOFError:
    pass

算法及复杂度

  • 算法：动态规划
  • 时间复杂度： 用于填充DP表，查询为 。由于数据是预处理的，总复杂度为 ，其中 是查询次数。
  • 空间复杂度： 用于存储DP表。