Keshawn_lu's Blog

牛客网 KY41.放苹果

字数统计: 562阅读时长: 2 min
2021/03/03 Share

题目简介:

把M个同样的苹果放在N个同样的盘子里,允许有的盘子空着不放,问共有多少种不同的分法?(用K表示)5,1,1和1,5,1 是同一种分法。

输入描述:

1
每行均包含二个整数M和N,以空格分开。1<=M,N<=10。

输出描述:

1
对输入的每组数据M和N,用一行输出相应的K。

输入

1
2
1
7 3

输出

1
8

思路:

n久没做动态规划的题了,又快忘光了…

首先dp[i][j]代表i个苹果装在j个盘子的方法数

我们可以这样想,装在j个盘子里有两种不同的装法:

  1. 至少有一个盘子是空的,那么我们把这个空的盘子扔掉,也不影响苹果怎么放,所以dp[i][j] = dp[i][j - 1](假设一个盘子是空的)
  2. 所有盘子里都有苹果,那么我们把所有盘子上的苹果都拿掉一个,也不影响最后的结果,所以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; //M个苹果, N个盘子
cin >> M >> N;

if (N > M) //盘子数大于苹果数,去掉多余的盘子不影响
N = M;

vector<vector<int>> dp(M + 1, vector<int>(N + 1)); //dp[i][j]代表i个苹果装在j个盘子的方法数

for (int i = 0; i <= N; i++)
dp[0][i] = 1; //0个苹果的情况,算一种方法

for (int i = 0; i <= M; i++)
dp[i][0] = 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;
}
CATALOG
  1. 1. 题目简介:
  2. 2. 输入描述:
  3. 3. 输出描述:
  4. 4. 输入
  5. 5. 输出
  6. 6. 思路:
  7. 7. 代码如下: