题解 | #放苹果#

递归版本

#include <stdio.h>

// 递归函数计算分苹果的方法数
int partition(int m, int n) {
    if (m == 0 || n == 1) {
        return 1; // 若苹果数为0或盘子数为1，只有一种分法
    }

    if (m < n) {
        return partition(m,m); 
        // 若苹果数小于盘子数，等同于每个盘子都盛放一个苹果
    } else {
        return partition(m, n - 1) + partition(m - n, n); 
        // 分为有一个盘子空着和每个盘子都有苹果两种情况
    }
}

int main() {
    int m, n;

    // 读取每行输入数据，计算分法并输出结果
    while (scanf("%d %d", &m, &n) != EOF) {
        int result = partition(m, n);
        printf("%d\n", result);
    }

    return 0;
}

动态规划版本

#include <stdio.h>

// 动态规划函数计算分苹果的方法数
int partition_dp(int m, int n) {
    int dp[11][11] = {0}; // 定义动态规划数组，dp[i][j]表示将i个苹果放入j个盘子的方法数

    // 初始化边界条件，若苹果数为0或盘子数为1，只有一种分法
    for (int i = 0; i <= m; i++) {
        dp[i][1] = 1;
    }
    for (int j = 1; j <= n; j++) {
        dp[0][j] = 1;
    }

    // 动态规划递推计算方法数
    for (int i = 1; i <= m; i++) {
        for (int j = 2; j <= n; j++) {
            if (i >= j) {
                dp[i][j] = dp[i][j-1] + dp[i-j][j]; // 分为有一个盘子空着和每个盘子都有苹果两种情况
            } else {
                dp[i][j] = dp[i][i]; // 若苹果数小于盘子数，等同于每个盘子都盛放一个苹果
            }
        }
    }

    return dp[m][n]; // 返回最终计算得到的结果
}

int main() {
    int m, n;

    // 读取每行输入数据，计算分法并输出结果
    while (scanf("%d %d", &m, &n) != EOF) {
        int result = partition_dp(m, n);
        printf("%d\n", result);
    }

    return 0;
}