题目链接

放苹果

题目描述

我们需要将 个相同的苹果放入 个相同的盘子中，允许有的盘子空着不放。求解有多少种不同的分法。（注意：由于苹果和盘子都是相同的，所以 和 是同一种分法）。

解题思路

这是一个经典的整数划分问题。问题等价于：将整数 划分为最多 个正整数之和的方案数。我们可以使用动态规划或递归来解决。

我们定义一个函数 ，表示将 个苹果放入 个盘子的方法数。我们可以根据盘子是否为空，以及苹果和盘子的数量关系，将问题分解为更小的子问题。

可以分为以下几种情况进行讨论：

  1. 边界情况

    • 当没有苹果时 ()，只有一种分法（所有盘子都为空），即 。
    • 当只有一个盘子时 ()，也只有一种分法（所有苹果都放入这一个盘子），即 。

  2. 苹果数小于盘子数 ()

    • 在这种情况下，最多只能使用 个盘子，因为即使每个盘子只放一个苹果，也至少有 个盘子是空的。由于盘子是相同的，这些多余的空盘子不影响分法。因此，将 个苹果放入 个盘子等价于将 个苹果放入 个盘子。
    • 所以，。

  3. 苹果数大于等于盘子数 ()

    • 这种情况可以分为两个互斥的子集：
      • 至少有一个盘子为空：由于盘子相同，这等价于将 个苹果放入 个盘子中。方法数为 。
      • 所有盘子都不为空：这意味着每个盘子都至少有一个苹果。我们可以先给每个盘子放上一个苹果，这样就用掉了 个苹果。剩下的 个苹果可以任意放入 个盘子中（此时允许有空盘）。方法数为 。
    • 根据加法原理，总方法数是这两个子集之和。
    • 所以，。

综上，我们可以得到完整的递推关系，并使用递归（配合记忆化搜索）或动态规划来求解。

代码

#include <iostream>
#include <vector>

using namespace std;

int solve(int m, int n) {
    if (m == 0 || n == 1) {
        return 1;
    }
    if (n > m) {
        return solve(m, m);
    } else {
        return solve(m, n - 1) + solve(m - n, n);
    }
}

int main() {
    int m, n;
    while (cin >> m >> n) {
        cout << solve(m, n) << endl;
    }
    return 0;
}

import java.util.Scanner;

public class Main {
    private static int solve(int m, int n) {
        if (m == 0 || n == 1) {
            return 1;
        }
        if (n > m) {
            return solve(m, m);
        } else {
            return solve(m, n - 1) + solve(m - n, n);
        }
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        while (sc.hasNextInt()) {
            int m = sc.nextInt();
            int n = sc.nextInt();
            System.out.println(solve(m, n));
        }
    }
}

def solve(m, n):
    if m == 0 or n == 1:
        return 1
    if n > m:
        return solve(m, m)
    else:
        return solve(m, n - 1) + solve(m - n, n)

def main():
    try:
        while True:
            line = input()
            if not line:
                break
            m, n = map(int, line.split())
            print(solve(m, n))
    except EOFError:
        pass

if __name__ == "__main__":
    main()

算法及复杂度

  • 算法：递归 / 动态规划
  • 时间复杂度：未经优化的递归会导致大量重复计算。如果使用记忆化搜索或动态规划表格，每个状态 只会被计算一次。因此，总时间复杂度为 。
  • 空间复杂度：如果使用动态规划表格，空间复杂度为 。如果使用递归，递归调用的深度栈也大致是这个量级。