LeetCode2928-给小朋友们分糖果I

儿童节特辑🤓

给你两个正整数 n 和 limit 。

请你将 n 颗糖果分给 3 位小朋友，确保没有任何小朋友得到超过 limit 颗糖果，请你返回满足此条件下的 总方案数 。

示例 1：

输入：n = 5, limit = 2
输出：3
解释：总共有 3 种方法分配 5 颗糖果，且每位小朋友的糖果数不超过 2 ：(1, 2, 2) ，(2, 1, 2) 和 (2, 2, 1) 。

示例 2：

输入：n = 3, limit = 3
输出：10
解释：总共有 10 种方法分配 3 颗糖果，且每位小朋友的糖果数不超过 3 ：(0, 0, 3) ，(0, 1, 2) ，(0, 2, 1) ，(0, 3, 0) ，(1, 0, 2) ，(1, 1, 1) ，(1, 2, 0) ，(2, 0, 1) ，(2, 1, 0) 和 (3, 0, 0) 。

提示：

1 <= n <= 50
1 <= limit <= 50

解法一：枚举

题目数据很小所以可以直接两层循环遍历。

class Solution {
public:
    int distributeCandies(int n, int limit) {
        int ans = 0;
        for (int i = 0; i <= limit; i++) {
            for (int j = 0; j <= limit; j++) {
                if (i + j > n) {
                    break;
                }
                if (n - i - j <= limit) {
                    ans++;
                }
            }
        }
        return ans;
    }
};

解法二：优化枚举

枚举第一个小朋友分得 $x$ 颗糖果，那么还剩下 $n−x$ 颗糖果，此时有两种情况：

$n−x>limit×2$，至少有一个小朋友会分得大于 $limit$ 颗糖果，此时不存在合法方案。
$n−x<=limit×2$，对于第二个小朋友来说，至少得分得 $max⁡(0,n−x−limit)$ 颗糖果，才能保证第三个小朋友分得的糖果不超过 $limit$ 颗。同时至多能拿到 $min⁡(limit,n−x)$ 颗糖果。

对于第二种情况计算出所有的合法方案即可。

class Solution {
public:
    int distributeCandies(int n, int limit) {
        int ans = 0;
        for (int i = 0; i <= min(limit, n); i++) {
            if (n - i > 2 * limit) {
                continue;
            }
            ans += min(n - i, limit) - max(0, n - i - limit) + 1;
        }
        return ans;
    }
};

解法三：容斥原理 | 隔板法

方法原理参考同站基础算法总结

本文采用署名-非商业性使用-相同方式共享 4.0 国际许可协议，转载请注明出处。