题目连接：http://ybt.ssoier.cn:8088/problem_show.php?pid=1192
一递归方式：视频讲解地址：https://www.bilibili.com/video/av27747114/?p=12
1 #include<bits/stdc++.h>
2 using namespace std;
3 int m,n;
4 int up(int m,int n)
5 {
6 if(m==0||n==1)return 1;
7 if(m<n)return up(m,m);
8 else return up(m,n-1)+up(m-n,n);
9 }
10 int main()
11 {
12 int s;
13 cin>>s;
14 while(s--)
15 {
16 cin>>m>>n;
17 cout<<up(m,n)<<endl;
18 }
19 return 0;
20 }二递推（简单动态规划），从某种意义讲递推和动归很难区分
1 #include<iostream>
2 #include<cstring>
3 using namespace std;
4 int a[20][20];//状态：a[m][n]表示m个苹果放在n个盘子里的方法数
5 int f(int m,int n)
6 {
7 int i,j;
8 for(i=1;i<=n;i++)//0个苹果
9 a[0][i]=1;
10 for(i=1;i<=m;i++)//1个盘子
11 a[i][1]=1;
12 for(i=1;i<=m;i++)
13 for(j=2;j<=n;j++)
14 if(i<j)
15 a[i][j]=a[i][i];
16 else
17 a[i][j]=a[i][j-1]+a[i-j][j]; //状态转移方程
18 }
19 int main()
20 {
21 int m,n,i,j,k;
22 cin>>k;
23 for(i=1;i<=k;i++)
24 {
25 cin>>m>>n;
26 f(m,n);
27 cout<<a[m][n]<<endl;
28 }
29 return 0;
30 }三、其他博客方法总结（摘自https://blog.csdn.net/QiaoRuoZhuo/article/details/80583072）
1 /*
2 Name: 放苹果问题集锦（每个盘子至少放1个苹果）
3 Copyright:
4 Author:
5 Date: 31-07-17 21:22
6 Description: 放苹果
7 查看 提交 统计 提问
8 总时间限制: 1000ms 内存限制: 65536kB
9 描述
10 把N个同样的苹果放在M个同样的盘子里，允许有的盘子空着不放，问共有多少种不同的分法？（用K表示）5，1，1和1，5，1 是同一种分法。
11 输入
12 第一行是测试数据的数目t（0 <= t <= 20）。以下每行均包含二个整数M和N，以空格分开。1<=M，N<=10。
13 输出
14 对输入的每组数据N和M，用一行输出相应的K。
15 样例输入
16 1
17 7 3
18 样例输出
19 4
20 算法思路：
21 回溯算法：有2种思路，一种是确保后面的盘子中苹果不比前面的少，另一种是确保后面的盘子中苹果不比前面的多。
22 第2种思路递归深度较少，但代码复杂些，特别要注意第n个盘子能放苹果的数量范围。
23 基本上递归问题都可以转化为记忆化搜索，然后转换为动态规划问题。
24 回溯算法相当于穷举，不但可以获得组合的数量，还可以存储具体的解空间。
25 记忆化搜索和动态规划算法均采用了确保后面的盘子中苹果不比前面的多的思路；其中动态规划进行了降维优化。
26 每个盘子至少放1个苹果和每个盘子至少放0个苹果的递归表达式以及边界条件都不一样。
27 */
28 #include<iostream>
29
30 using namespace std;
31
32 const int MAXN = 10; //苹果的最大数量
33 const int MAXM = 10; //盘子的最大个数
34 int A1[MAXN+1], A2[MAXN+1];
35 int M, N, s1, s2;
36 long long B[MAXM+1][MAXN+1]; //记录给定n个盘子装m个苹果的方案总数
37 long long B2[MAXM+1][MAXN+1]; //记录给定n个盘子装m个苹果的方案总数
38 long long pre[MAXN+1]; //记录给定n个盘子装m个苹果的方案总数
39 long long cur[MAXN+1]; //记录给定n个盘子装m个苹果的方案总数
40 long long F[MAXN+1]; //记录给定n个盘子装m个苹果的方案总数
41
42 void DFS_1(int k, int n); //n表示共n个苹果，k表示第k个盘子
43 void DFS_2(int k, int n); //n表示共n个苹果，k表示第k个盘子
44 long long Fun(int k, int n); //记忆化搜索
45 void Fun2(int k, int n); //动态规划：使用二维数组
46 long long Fun3(int k, int n); //动态规划：使用2个一维数组
47 long long Fun4(int k, int n); //动态规划：使用1个一维数组
48
49 int main()
50 {
51 int t;
52
53 Fun2(MAXM, MAXN);
54 cin >> t;
55 for (int k=0; k<t; k++)
56 {
57 cin >> N >> M;
58
59 s1 = 0;
60 DFS_1(1, N);
61 cout << s1 << endl;
62
63 s2 = 0;
64 int minNum = N/M + (N%M!=0);
65 for (A2[1]=N-M+1; A2[1]>=minNum; A2[1]--)//第一个盘中放A2[1]个苹果
66 {
67 DFS_2(2, N-A2[1]);
68 }
69 cout << s2 << endl;
70
71 cout << Fun(M, N) << endl;
72 cout << B2[M][N] << endl;
73 cout << Fun3(M, N) << endl;
74 }
75
76 return 0;
77 }
78
79 void DFS_1(int k, int n) //n表示共n个苹果，k表示第k个盘子
80 {
81 if (k == M)//最后一个盘子
82 {
83 A1[k] = n;
84 cout << s1 << " : ";
85 for (int i=1; i<=k; i++)
86 cout << A1[i] << " ";
87 cout << endl;
88 s1++;
89 }
90 else //至少还有2个盘子
91 {
92 for (A1[k]=max(1,A1[k-1]); A1[k]+A1[k]<=n; A1[k]++)
93 { //确保剩下的苹果不比当前盘子中的少
94 DFS_1(k+1, n-A1[k]);
95 }
96 }
97 }
98
99 void DFS_2(int k, int n) //n表示共n个苹果，k表示第k个盘子
100 {
101 if (n <= 0)
102 return;
103
104 if (k == M)//最后一个盘子
105 {
106 if (n > A2[k-1]) //确保后面的盘子中苹果不比前面的多
107 return;
108 A2[k] = n;
109 cout << s2 << " : ";
110 for (int i=1; i<=k; i++)
111 cout << A2[i] << " ";
112 cout << endl;
113 s2++;
114 }
115 else
116 {
117 int maxNum = min(n, A2[k-1]);//确保后面的盘子中苹果不比前面的多
118 for (A2[k]=maxNum; A2[k]>=1; A2[k]--)
119 {
120 DFS_2(k+1, n-A2[k]);
121 }
122 }
123 }
124
125 long long Fun(int k, int n) //记忆化搜索
126 {
127 if (B[k][n] != 0)
128 return B[k][n];
129 if (k == 1 || n == k)//只有1个盘子或者盘子与苹果数量相等
130 B[k][n] = 1;
131 else if (n < k) //苹果数量少于盘子
132 B[k][n] = 0;
133 else //两种情况：第k个盘子只放一个苹果；每个盘子至少放2个苹果，则每个盘子中拿走1个苹果后，分配方法数量不变
134 B[k][n] = Fun(k-1, n-1) + Fun(k, n-k);
135
136 return B[k][n];
137 }
138
139 void Fun2(int k, int n) //动态规划：使用二维数组
140 {
141 for (int j=1; j<=n; j++)//j个苹果放到1个盘子里
142 B2[1][j] = 1;
143 for (int i=2; i<=k; i++)
144 {
145 for (int j=i; j<=n; j++)
146 {
147 B2[i][j] = B2[i-1][j-1] + B2[i][j-i];
148 }
149 }
150 }
151
152 long long Fun3(int k, int n) //动态规划：使用2个一维数组
153 {
154 for (int j=1; j<=n; j++)//j个苹果放到1个盘子里
155 pre[j] = 1;
156 for (int i=2; i<=k; i++)
157 {
158 for (int j=1; j<i; j++) //苹果数量少于盘子
159 {
160 cur[j] = 0;
161 }
162 for (int j=i; j<=n; j++)
163 {
164 cur[j] = pre[j-1] + cur[j-i];
165 }
166 for (int j=1; j<=n; j++)
167 {
168 pre[j] = cur[j];
169 }
170 }
171
172 return pre[n];
173 }