解题思路

这是一个典型的动态规划问题，可以分为以下几种情况：

  1. 当苹果数 或盘子数 时，只有1种分法
  2. 当苹果数 时，必定有 个盘子为空，等价于把 个苹果放在 个盘子中
  3. 当苹果数 时，可以分两种情况：
    • 至少有一个空盘子：相当于
    • 所有盘子都有苹果：每个盘子先放一个，相当于

代码

#include <iostream>
using namespace std;

class Solution {
public:
    int putApple(int m, int n) {
        if (m == 0 || n == 1) return 1;
        if (m < n) return putApple(m, m);
        return putApple(m, n-1) + putApple(m-n, n);
    }
};

int main() {
    int m, n;
    while (cin >> m >> n) {
        Solution solution;
        cout << solution.putApple(m, n) << endl;
    }
    return 0;
}

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        while (sc.hasNext()) {
            int m = sc.nextInt();
            int n = sc.nextInt();
            Solution solution = new Solution();
            System.out.println(solution.putApple(m, n));
        }
    }
}

class Solution {
    public int putApple(int m, int n) {
        if (m == 0 || n == 1) return 1;
        if (m < n) return putApple(m, m);
        return putApple(m, n-1) + putApple(m-n, n);
    }
}

def putApple(m, n):
    if m == 0 or n == 1:
        return 1
    if m < n:
        return putApple(m, m)
    return putApple(m, n-1) + putApple(m-n, n)

while True:
    try:
        m, n = map(int, input().split())
        print(putApple(m, n))
    except:
        break

算法及复杂度

  • 算法：递归实现的动态规划
  • 时间复杂度： - 每个状态最多计算一次
  • 空间复杂度： - 递归调用栈的深度