HJ61 放苹果-移动平台-IT技术

描述：

把m个同样的苹果放在n个同样的盘子里，允许有的盘子空着不放，问共有多少种不同的分法？（用K表示）5，1，1和1，5，1 是同一种分法。

数据范围：

根据m和n的关系：

1、苹果的数量少于盘子时，即 m < n --> dp[i][j] = dp[i][i]

2、苹果的数量大于等于盘子时，分两种情况：

　　1) 没有空盘子时，则从每个盘子中拿走一个苹果，摆放的方法数是一样的。dp[i][j] = dp[i - j][j]

2) 有空盘子时，此种情况不太好理解：有一个空盘子时 dp[i][j] = dp[i][j - 1]。其实这里的有一个空盘子，是个递归的过程dp[i][j - 1] 包含了dp[i][j - 2]，以此类推：dp[i][j - 1]，包含了 j - 1，... , 1个空盘子的情况

　　　　--> 有空盘子时，dp[i][j] = dp[i][j - 1];

　　--> m >= n 时， dp[i][j] = dp[i - j][j] + dp[i][j - 1]；

边界条件：

1、0个盘子时，当然没法摆了，只能是0： dp[i][0] = 0;

2、一个盘子时，所有的苹果只能放到这一个盘子中：dp[i][1] = 1

3、0个苹果时，所有盘子都是空的：dp[0][j] = 1;

#include <bits/stdc++.h>

using namespace std;

int main() {
    int m, n;
    while (cin >> m >> n) {
        vector<vector<int>> dp(m + 1, vector<int>(n + 1, 0)); // m个苹果，放到n个盘子中
        
        // 0个盘子和一个盘子时，只有一种方法
        for (int i = 0; i <= m; i++) {
            dp[i][0] = 0;
            dp[i][1] = 1;
        }
        
        // 0个苹果时
        for (int i = 0; i <= n; i++) {
            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][i];
                } else {
                    dp[i][j] = dp[i - j][j] + dp[i][j - 1];
                }
            }
        }
        cout << dp[m][n] << endl;
    }
    
    return 0;
}

本文摘自：https://www.cnblogs.com/

HJ61 放苹果2022-02-14 10:50:49

HJ61 放苹果
2022-02-14 10:50:49