文章目录

• 题目描述
• 题解
• 思路1 暴力递归
• 思路2：缓存思想——动态规划来优化暴力递归

题目描述

链接：点我做题

题解

思路1 暴力递归

  我们利用递归来解决这个问题，不妨这样思考，假设apples表示当前剩余的苹果数，plates表示当前剩余的盘子数，ways(apples, plates)表示以apples个苹果放进plates个盘子里的方法数。
  如果apples==0，说明当前苹果都已经放完了，既然放完了，不管剩不剩盘子，这都是一种放的方法，向上一层返回1；
  否则apples不为0的时候，如果plates==0了，盘子已经被用完了但是苹果没放完，这种情况显然是摆放失败了，不是一种摆放的方法，向上一层返回0;
  再考虑一种特殊情况，当盘子数大于苹果数时，那么苹果怎样也不可能放到多出来的盘子上，这种情况下的摆放方法数显然和盘子减少为$plates-apples$个，apples个苹果的摆放方法数是一样多的，因此
$$\begin{gathered} if(apples<plates), \\ ways(apples,plates)=ways(apples,plates-apples) \end{gathered}$$
  当剩余的苹果数量大于盘子数量时，我们有两种互斥的摆法：
  一种，我们用上所有的盘子,也就是先让所有的盘子都摆上一个苹果，那么这种方式的摆法数量a显然等于$ways(apples-plates,plates)$;
  另一种方法，我们不用上所有的盘子，那么怎么才能不用上所有的盘子呢？先放弃一个盘子，剩下的盘子是放弃还是保留交给递归来讨论。也就是说，不完全使用所有盘子的摆放方法数量b等于$ways(apples,plates-1)$.
  这两种情况显然是互斥的，所以他们的方法数可以直接相加，也就是说
$$\begin{gathered} if(apples>plates) \\ ways(apples,plates)=ways(apples-plates,plates) \\ +ways(apples,plates-1) \end{gathered}$$
代码：

int ways(int apples, int plates) {//apples个完全相同的苹果放到plates个完全相同的盘子里//有多少种方法//如果苹果用完了 说明摆放结束了 返回一种摆法if (apples == 0) {return 1;}//如果plates等于0了 apples不等于0还 那么说明没有盘子用了//0种摆法if (plates == 0) {return 0;}//如果盘子数大于苹果数 那么多出来的盘子不论什么摆法一定空着//这种情况下的摆法数等于把多出来的盘子都不考虑的摆法数if (plates > apples) {return ways(apples, apples);}//当苹果数大于盘子数的时候 有两种方法//1) 我们把所有的盘子都使用 那么相当于先往所有盘子上都放一个苹果// 这种方法的方法数等于ways(apples - plates, plates)int a = ways(apples - plates, plates);//2) 我们让盘子不全都使用 那么就敲碎一个盘子 //剩下的盘子全用还是敲碎一个 总可能方法数用递归去讨论int b = ways(apples, plates - 1);//这两种情况显然是互斥的 所以数量可以直接加return a + b; }

思路2：缓存思想——动态规划来优化暴力递归

  所有的暴力递归的展开过程都可以用动态规划来优化.我们想想递归是怎么解决问题的，比如遇到ways(7, 5)，它是展开为ways(7,4)和ways(2,5)来解决的，然后ways(2,5)和ways(7,4)再接着展开，那如果我们之前早就计算过ways(2,5)了呢,如果已经计算过一次了，还有必要再接着展开吗？直接用上次计算的结果不就好了，这样不就可以把递归层数变浅了吗。
  那么怎么记录上次计算的结果呢？这里可以用一个二维数组dp缓存存起来，并且考虑到多组输入问题，我们可以把创建二维数组dp的过程放到执行ways方法外头，这样下一组输入也可以使用我们上一轮计算过的值。
  为了和0种方法区分，我们不妨先让dp的所有值都赋-1，表示尚未计算过，在递归的每一层都检查当前层中dp的是否不等于-1，如果是，说明这层没必要继续展开下去了，已经计算过了，返回$dp[apples][plates]$,否则再执行展开过程，并且最后把这一层的计算结果记录到dp中作为缓存。

代码：

#include <vector> #include <iostream> using namespace std; int ways(int apples, int plates, vector<vector<int>>& dp) {if (dp[apples][plates] != -1){return dp[apples][plates];}int ans = 0;if (apples == 0){ans = 1;}else if (plates == 0){ans = 0;}else if (apples < plates){ans = ways(apples, apples, dp);}else{int a = ways(apples - plates, plates, dp);int b = ways(apples, plates - 1, dp);ans = a + b;}dp[apples][plates] = ans;return ans; }int main() {int apples, plates;vector<vector<int>> dp(11, vector<int>(11, -1));while (cin >> apples >> plates){cout << ways(apples, plates, dp) << endl;}return 0; }

总结

以上是生活随笔为你收集整理的算法题放苹果：把M个相同的苹果放到N个完全相同的盘子里，有多少种放法?的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。