Easy

题目描述

给你两个正整数 n 和 limit。

返回在 3 个儿童之间分发 n 个糖果的总方案数，使得没有儿童获得超过 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

解题思路

这是一道组合数学问题，要求计算在限制条件下的分配方案数。

思路分析：

由于数据范围较小（n ≤ 50，limit ≤ 50），可以使用暴力枚举的方法。我们需要找到所有满足以下条件的三元组 (x, y, z)：

  1. x + y + z = n（总糖果数为 n）
  2. 0 ≤ x, y, z ≤ limit（每个儿童最多 limit 个糖果）

解法一：三重循环暴力枚举 使用三层嵌套循环，枚举前两个儿童可能得到的糖果数量，第三个儿童的糖果数量由前两个确定。只需检查第三个儿童是否也满足限制条件即可。

解法二：数学公式（容斥原理） 可以使用容斥原理计算，但对于这个问题规模，暴力枚举更直观且效率足够。

由于约束条件简单且数据规模小，推荐使用暴力枚举解法，代码简洁易懂。

代码实现

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

class Solution:
    def distributeCandies(self, n: int, limit: int) -> int:
        count = 0
        for i in range(limit + 1):
            for j in range(limit + 1):
                k = n - i - j
                if 0 <= k <= limit:
                    count += 1
        return count

public class Solution {
    public int DistributeCandies(int n, int limit) {
        int count = 0;
        for (int i = 0; i <= limit; i++) {
            for (int j = 0; j <= limit; j++) {
                int k = n - i - j;
                if (k >= 0 && k <= limit) {
                    count++;
                }
            }
        }
        return count;
    }
}

var distributeCandies = function(n, limit) {
    let count = 0;
    for (let i = 0; i <= limit; i++) {
        for (let j = 0; j <= limit; j++) {
            let k = n - i - j;
            if (k >= 0 && k <= limit) {
                count++;
            }
        }
    }
    return count;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型值
时间复杂度O(limit²)
空间复杂度O(1)

相关题目