描述

题目描述

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

示例

输入：
7 3
输出：
8

知识点：递归，动态规划

难度：⭐⭐

题解

方法一：递归

解题思路：

通过递归，定义好递归的功能以及设置递归终止条件，对盘子数量和苹果数量界限做好判断，结合题目对于m和n的要求，可以通过递归分情况得出结果

算法流程：

• 定义递归功能：当前持有m个苹果，有n个盘子可供存放，返回摆放方案数
• 设置递归出口：
  • 当苹果数m=0， 此时表示什么都不做，输出1种方案，再递归下去m<0，题目要求m>=0
  • 当盘子只有一个时，剩下的苹果m只能全部摆放这个盘子，递归返回1种方案，再递归下去n==0, 题目要求n>=1
• 两种进入递归的情况：
  • 当盘子数大于苹果数，一定有n-m个盘子空着，而且每个盘子都一样，因此count(m,n)==count(m,n-1)
  • 当盘子数<=苹果数，有两种情况：
    • 1.至少有一个盘子可以不放，因此count(m, n-1)，继续递归
    • 2.至少每个盘子都有一个苹果，摆放后苹果数为(m-n)，因此coutn(m-n, n)

Java 版本代码如下：

import java.util.*;
public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        while (scanner.hasNext()){
        	int m = scanner.nextInt();
        	int n = scanner.nextInt();
        	System.out.println(count(m, n));
        }
    }

    // 递归功能：当前持有m个苹果，有n个盘子可供存放，返回摆放方案数
    private static int count(int m, int n) {
        // 递归出口：当苹果数m=0， 此时表示什么都不做，输出1种方案，再递归下去m<0，题目要求m>=0
        // 当盘子只有一个时，剩下的苹果m只能全部摆放这个盘子，递归返回1种方案，再递归下去n==0, 题目要求n>=1
        if(m == 0 || n == 1) {
            return 1;
        }
        // 当盘子数大于苹果数，一定有n-m个盘子空着，而且每个盘子都一样，因此count(m,n)==count(m,n-1)
        if(n > m) {
            return count(m, n-1);
        } else {
            // 当盘子数<=苹果数，有两种情况：
            // 1.至少有一个盘子可以不放，因此count(m, n-1)
            // 2.至少每个盘子都有一个苹果，摆放后苹果数为(m-n)，因此coutn(m-n, n)
            return count(m, n - 1) + count(m - n, n);
        }
    }
}
        

复杂度分析：

时间复杂度：$O(2^n)O(2^n)$，树型递归，最大深度为N，总共递归$2^{N}2^N$次

空间复杂度：$O(n)O(n)$，递归栈的深度不超过树高，即不超过盘子数n

方法二：动态规划

解题思路：

首先我们用一个二维数组来表示摆放的方案数：持有i个苹果，有j个盘子可以存放苹果，总共有 dp[i][j]种方法。

状态转移方程：dp[i][j] = dp[i][j-1] + dp[i-j][j];

对于状态转移，有两种情况：

1. 如果苹果数 < 盘子数，则表示有空盘，则忽略一个盘子，在n-1个放苹果，一直递推到n==1，有一种摆法
2. 如果苹果数 >= 盘子数，可以看作没有空盘
   1. 则可以选择忽略一个盘子，如上边做法
   2. 还可以选择每个盘子放一个苹果，即苹果数剩下i-j,继续递推直到j==1

算法流程：

• 定义二维的dp数组：持有i个苹果，有j个盘子可以存放苹果，总共有 dp[i][j]种方法
• 设置 base case：没有苹果，只有一种摆放方法，可以作为递推的终止结果
• 状态转移方程：dp[i][j] = dp[i][j-1] + dp[i-j][j];
  • 当苹果数 < 盘子数，有空盘，则忽略一个盘子，在n-1个放苹果，一直递推到n==1，有一种摆法
  • 苹果数 >= 盘子数，可以看作没有空盘。则可以选择忽略一个盘子，如上边做法。还可以选择每个盘子放一个苹果，即苹果数剩下i-j,继续递推直到j==1

Java 版本代码如下：

import java.util.*;
public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        while (scanner.hasNext()){
        	int m = scanner.nextInt();
        	int n = scanner.nextInt();
        	System.out.println(count(m, n));
        }
    }

    private static int count(int m, int n) {
        // 持有i个苹果，有j个盘子可以存放苹果，总共有 dp[i][j]种方法
        int[][] dp = new int[m+1][n+1];
        // base case：没有苹果，只有一种摆放方法，可以作为下面递推的终止结果
        for(int j = 0; j <= n; j++) {
            dp[0][j] = 1;
        }
        for(int i = 1; i <= m; i++) {
            for(int j = 1; j <= n; j++) {
                if(i < j) {
                    // 苹果数 < 盘子数，有空盘，
                    // 则忽略一个盘子，在n-1个放苹果，一直递推到n==1，有一种摆法
                    dp[i][j] = dp[i][j-1];
                } else {
                    // 苹果数 >= 盘子数，可以看作没有空盘
                    // 则可以选择忽略一个盘子，如上边做法
                    // 还可以选择每个盘子放一个苹果，即苹果数剩下i-j,继续递推直到j==1
                    dp[i][j] = dp[i][j-1] + dp[i-j][j];
                }
            }
        }
        return dp[m][n];
    }
}
        

复杂度分析：

时间复杂度：$O(m\ast n)O(m*n)$，进行两层循环，通过穷举需要进行两层for循环实现递推

空间复杂度：$O(m\ast n)O(m*n)$，维护二维数组保存状态