题目简介:
把M个同样的苹果放在N个同样的盘子里,允许有的盘子空着不放,问共有多少种不同的分法?(用K表示)5,1,1和1,5,1 是同一种分法。
输入描述:
1
| 每行均包含二个整数M和N,以空格分开。1<=M,N<=10。
|
输出描述:
输入
输出
思路:
n久没做动态规划的题了,又快忘光了…
首先dp[i][j]
代表i
个苹果装在j
个盘子的方法数
我们可以这样想,装在j
个盘子里有两种不同的装法:
- 至少有一个盘子是空的,那么我们把这个空的盘子扔掉,也不影响苹果怎么放,所以
dp[i][j] = dp[i][j - 1]
(假设一个盘子是空的)
- 所有盘子里都有苹果,那么我们把所有盘子上的苹果都拿掉一个,也不影响最后的结果,所以
dp[i][j] = dp[i - j][j]
最后将这两种情况的方法数相加即可。
tip:
- 没有苹果的情况下,算一种方法
- 没有盘子的情况下,算零种方法
代码如下:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45
| #include <iostream> #include <string> #include <vector> #include <algorithm> #include <unordered_map> #include <cmath> #include <iomanip> #include <set> #include <map>
using namespace std;
int main() {
int M, N; cin >> M >> N;
if (N > M) N = M;
vector<vector<int>> dp(M + 1, vector<int>(N + 1));
for (int i = 0; i <= N; i++) dp[0][i] = 1;
for (int i = 0; i <= M; i++) dp[i][0] = 0;
for (int i = 1; i <= M; i++) {
for (int j = 1; j <= N; j++) {
dp[i][j] = dp[i][j - 1];
if (i >= j) dp[i][j] += dp[i - j][j]; } }
cout << dp[M][N] << endl; }
|