HJ61 放苹果

#HJ61 放苹果

描述

把m个同样的苹果放在n个同样的盘子里，允许有的盘子空着不放，问共有多少种不同的分法？

注意：如果有7个苹果和3个盘子，（5，1，1）和（1，5，1）被视为是同一种分法。

数据范围：0≤m≤10 0≤m≤10 ，1≤n≤10 1≤n≤10 。

示例：

输入：

7 3

输出：

8

思路：

因为不区分顺序，所以只考虑苹果分了几份，每份多少个。

很容易我们知道当苹果为 0 或者盘子只有 1 个时候，只有 1 种分法。

我们再来分析下，假如盘子的数量比苹果的数量多，假设有 2个苹果，3 个盘子，我们是不是最多放 2 个盘子，换句话就是说至少有 3 - 2 个盘子是空的，分法只能在 2 个盘子中进行。

那苹果的数量大于等于盘子的时候呢，假如 5 个苹果，3 个盘子，可以分成两类：

• 至少有一个盘子空着，那就变成 5 个苹果，2 个盘子的分法。
• 全部盘子都有苹果，那就变成了 （5 - 3）= 2 个苹果， 3个盘子的分法。

综上：

第一步：明确「状态」和「选择」：

状态就是 有 i 个盘子， j 个苹果，选择就是放在哪个盘子

第二步：明确 dp 定义：

我们可以定义一个 dp数组，dp[i][j]的定义：

表示 i 个苹果， j 个苹果，共有 dp[i][j]种分法。

第三步：根据定义明确状态转移：

• 当苹果 m > 盘子 n 时

  ​ $ dp[i][j] = dp[i][j - 1] $

• 当苹果 m <= 盘子 n 时

  $ dp[i][j] = dp[i][j - 1] + do[i - j][j] $

代码：

#include <bits/stdc++.h>
using namespace std;

int main(){
    int m, n;
    cin >> m >> n;
    vector<vector<int> > dp(m + 1, vector<int>(n + 1, 0));
    
    // base case
    for(int i = 0; i <= m; i++){
        //只有一个盘子
        dp[i][1] = 1;
    }
    for(int i = 0; i <= n; i++){
        //0个苹果
        dp[0][i] = 1;
    }
    for(int i = 1; i <= m; i++){
        for(int j = 1; j <= n; j++){
            if(i < j){
                dp[i][j] = dp[i][j - 1];
            }else{
                dp[i][j] = dp[i][j - 1] + dp[i - j][j];
            }
        }
    }
    cout << dp[m][n] << endl;
    return 0;
}