华为OD机考题(HJ61 放苹果)

前言

经过前期的数据结构和算法学习，开始以OD机考题作为练习题，继续加强下熟练程度。

描述

把m个同样的苹果放在n个同样的盘子里，允许有的盘子空着不放，问共有多少种不同的分法？

注意：如果有7个苹果和3个盘子，（5，1，1）和（1，5，1）被视为是同一种分法。

数据范围：0≤𝑚≤10 0≤m≤10 ，1≤𝑛≤10 1≤n≤10 。

输入描述：

输入两个int整数

输出描述：

输出结果，int型

示例1

输入：

7 3

输出：

8

实现原理与步骤

我们需要计算有多少种不同的方式把m个苹果放到n个盘子里。以下是问题的递归公式：

• 如果没有苹果（m == 0），只有一种放法，就是不放。
• 如果只有一个盘子（n == 1），只有一种放法，就是把所有苹果放到这个盘子里。
• 如果盘子数多于苹果数（n > m），可以等同于n = m的情况，因为多余的盘子可以为空。
• 否则，分为两种情况：放至少一个苹果到每个盘子，或者不放苹果到第n个盘子。

递归公式：

实现代码(递归)

public class Main {public static void main(String[] args) {int m = 7; // 苹果数int n = 3; // 盘子数System.out.println("Total ways to place apples: " + placeApples(m, n));}public static int placeApples(int m, int n) {// 如果苹果数为0，只有一种放置方法，不放苹果if (m == 0) {return 1;}// 如果只有一个盘子，只有一种放置方法，把所有苹果放到这个盘子里if (n == 1) {return 1;}// 如果盘子数大于苹果数，相当于盘子数等于苹果数if (n > m) {return placeApples(m, m);}// 否则，递归计算放苹果的方法数return placeApples(m, n - 1) + placeApples(m - n, n);}
}

实现代码(动态规划)

public class Main {public static void main(String[] args) {int m = 7; // 苹果数int n = 3; // 盘子数System.out.println("Total ways to place apples: " + placeApplesDP(m, n));}public static int placeApplesDP(int m, int n) {int[][] dp = new int[m + 1][n + 1];for (int i = 0; i <= m; i++) {dp[i][1] = 1; // 只有一个盘子的情况}for (int j = 0; j <= n; j++) {dp[0][j] = 1; // 没有苹果的情况}for (int i = 1; i <= m; i++) {for (int j = 2; j <= n; j++) {if (j > i) {dp[i][j] = dp[i][i];} else {dp[i][j] = dp[i][j - 1] + dp[i - j][j];}}}return dp[m][n];}
}