先引入一个比较实际的问题:分苹果
题目
- M个相同苹果放到N个相同篮子里有多少种放法,允许有篮子不放。
- 1<=M<=10,1<=N<=10
- 例如5个苹果三个篮子,3,1,1 和 1,1,3是同一种放法
- 输入 7 3
- 输出 8
思路
设f(m,n) 为m个苹果,n个盘子的放法数目:
当n>m:必定有n-m个盘子永远空着,去掉它们对摆放苹果方法数目不产生影响。即if(n>m) f(m,n) = f(m,m)
当n<=m:不同的放法可以分成两类:
(1)有至少一个盘子空着,即相当于f(m,n) = f(m,n-1);
(2)所有盘子都有苹果,相当于可以从每个盘子中拿掉一个苹果,不影响不同放法的数目,即f(m,n) = f(m-n,n).而总的放苹果的放法数目等于两者的和,即 f(m,n) =f(m,n-1)+f(m-n,n)
递归出口条件说明:
- 当n=1时,所有苹果都必须放在一个盘子里,所以返回1;
- 当没有苹果可放时,定义为1种放法;
- 递归的两条路,第一条n会逐渐减少,终会到达出口n==1;
- 第二条m会逐渐减少,因为n>m时,我们会return f(m,m) 所以终会到达出口m==0.
代码
- #include <iostream>
- #include <string>
- #include <vector>
- #include <stack>
- #include <algorithm>
- using namespace std;
- // apple 个 苹果 basket 个 篮子
- int ShareApple(int apple,int basket){
- // 因为我们总是让apple >= basket来求解的,所以apple - basket >= 0,
- // 让apple = 0时候结束,如果改为apple = 1,可能得不到正确解
- if(apple == 0 || basket == 1){
- return 1;
- }//if
- // 篮子多于苹果 按照苹果个数分
- else if(apple < basket){
- return ShareApple(apple,apple);
- }//else
- return ShareApple(apple,basket-1) + ShareApple(apple - basket,basket);
- }
- int main(){
- int apple,basket;
- //freopen("C:\\Users\\Administrator\\Desktop\\acm.txt","r",stdin);
- while(cin>>apple>>basket){
- cout<<ShareApple(apple,basket)<<endl;
- }//while
- return 0;
- }
经典问题:整数划分
/*
整数划分
(一)将n划分成若干不同整数之和的划分数
(二)将n划分成若干正整数之和的划分数
(三)将n划分成k个正整数之和的划分数
(四)将n划分成最大数不超过k的划分数
(五)将n划分成若干个 奇正整数之和的划分数
*/
- #include<iostream>
- #include<cstdio>
- #include<cstdlib>
- #include<cmath>
- #include<cstring>
- #include<vector>
- #include<queue>
- #include<set>
- #include<map>
- #include<algorithm>
- #include<sstream>
- #define eps 1e-9
- #define pi acos(-1)
- #define INF 0x7fffffff
- #define inf -INF
- #define MM 12900
- #define N 50
- using namespace std;
- typedef long long ll;
- const int _max = N + 10;
- int dp[_max][_max],n,k,out[6];
- int main(){
- #ifndef ONLINE_JUDGE
- freopen("input.txt","r",stdin);
- #endif // ONLINE_JUDGE
- while(scanf("%d%d",&n,&k)==2){
- /*****************整数划分(二)******************/
- memset(dp,0,sizeof(dp));
- dp[0][0] = 1;
- for(int i = 0; i <= n; ++ i)
- for(int j = 1; j <= n; ++ j){
- if(j>i)dp[i][j]=dp[i][i];
- else dp[i][j] = dp[i-j][j] + dp[i][j-1];
- }
- out[1] = dp[n][n];
- /*****************整数划分(四)******************/
- out[3] = dp[n][k];
- /*****************整数划分(三)******************/
- memset(dp,0,sizeof(dp));
- dp[0][0] = 1;
- for(int i = 1; i <= N; ++ i)
- for(int j = 1; j <= i; ++ j){
- dp[i][j] = dp[i-1][j-1]+dp[i-j][j];
- }
- out[2] = dp[n][k];
- /*****************整数划分(五)******************/
- memset(dp,0,sizeof(dp));
- dp[0][0] = 1;
- for(int i = 0; i <= n; ++ i)
- for(int j = 1; j <= n; ++ j){
- if(j&1){
- if(j>i)dp[i][j] = dp[i][i];
- else dp[i][j] = dp[i-j][j]+dp[i][j-1];
- }
- else dp[i][j] = dp[i][j-1];
- }
- out[4] = dp[n][n];
- /*****************整数划分(一)******************/
- memset(dp,0,sizeof(dp));
- dp[0][0] = 1;
- for(int i = 0; i <= n; ++ i)
- for(int j = 1; j <= n; ++ j){
- if(j>i)dp[i][j]=dp[i][i];
- else dp[i][j] = dp[i-j][j-1] + dp[i][j-1];
- }
- out[5] = dp[n][n];
- /*****************输出******************/
- for(int i = 1; i<= 5; ++ i)
- printf("%d\n",out[i]);
- printf("\n");
- }
- return 0;
- }
- /*
- /*****(一)将n划分成若干不同整数之和的划分数************
- dp[i][j]表示将整数i划分成不超过j的划分数,分含不含j两种情况
- dp[0][0] = 1
- dp[i][j] = dp[i-j][j-1] + dp[i][j-1];(j<=i)
- = dp[i][i] (j >i)
- =>ans = dp[n][n]
- /*****(二)将n划分成若干正整数之和的划分数*************
- dp[i][j]表示将整数i划分成不超过j的划分数,分含不含j两种情况
- 与(一)区别,j可重复
- dp[0][0] = 1
- dp[i][j] = dp[i-j][j] + dp[i][j-1];(j<=i)
- = dp[i][i] (j >i)
- =>ans = dp[n][n]
- /*****(三)将n划分成k个正整数之和的划分数*************
- dp[i][j]表示将整数i划分成j个正整数的划分数,考虑j组数中含不含1
- dp[0][0] = 1
- dp[i][j] = dp[i-1][j-1] + dp[i-j][j];
- 如果不包含1,那么每组数至少为2,从每堆数中各拿出1还能够成j堆数dp[i-j][j]
- =>ans = dp[n][k]
- /*****(四)将n划分成最大数不超过k的划分数************
- dp[i][j]表示将整数i划分成不超过j的划分数,分含不含j两种情况
- 是(二)的特例
- dp[0][0] = 1
- dp[i][j] = dp[i-j][j] + dp[i][j-1];(j<=i)
- = dp[i][i] (j >i)
- =>ans = dp[n][k]
- /*****(五)将n划分成若干个 奇正整数之和的划分数******
- dp[i][j]表示将整数i划分成不超过j的划分数,分含不含j两种情况
- dp[0][0] = 1;
- j是奇数,正常判断
- dp[i][j] = dp[i-j][j] + dp[i][j-1];(j<=i)
- = dp[i][i] (j >i)
- j是偶数,dp[i][j] = dp[i][j-1]//往下递推
- =>ans = dp[n][n]
- */
联系客服