难度: Easy
给你两个正整数 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 <= 501 <= limit <= 50运行时间: 22 ms
内存: 15.9 MB
def C2(n):
return n * (n - 1) // 2 if n >= 1 else 0
class Solution:
def distributeCandies(self, n: int, limit: int) -> int:
return C2(n + 2) - 3 * C2(n + 2 - (limit + 1)) + 3 * C2(n + 2 - 2 * (limit + 1)) - C2(n + 2 - 3 * (limit + 1))
该题解使用了组合数学中的Stars and Bars定理来解决分糖果问题。Stars and Bars定理用于计算将n个相同的物体分配到k个不同的箱子中的方式数。在本题中，我们需要将n颗糖果分给3个小朋友，并满足每位小朋友的糖果数不超过limit。首先，计算不考虑限制的分配方法数，然后使用容斥原理（Inclusion-Exclusion Principle）来去除那些违反条件的分配情况。具体来说，先计算所有可能的分配方法数，再减去至少有一位小朋友得到超过limit颗糖果的情况，然后加上至少有两位小朋友得到超过limit的情况，最后减去所有三位小朋友都得到超过limit颗糖果的情况。
时间复杂度: O(1)
空间复杂度: O(1)
def C2(n):
# 计算从n个不同的物体中选择两个物体的组合数，即C(n, 2)
return n * (n - 1) // 2 if n >= 1 else 0
class Solution:
def distributeCandies(self, n: int, limit: int) -> int:
# 计算总方案数，使用Stars and Bars方法结合容斥原理
return C2(n + 2) - 3 * C2(n + 2 - (limit + 1)) + 3 * C2(n + 2 - 2 * (limit + 1)) - C2(n + 2 - 3 * (limit + 1))
在本题中，计算至少有一个小朋友得到超过limit颗糖果的情况时，`3`代表三种可能的情况——每一位小朋友可能是超过limit的那一位。`limit + 1`是因为我们要计算某个小朋友获得的糖果数超过limit，即至少是`limit + 1`颗。对于这样的情况，我们需要从总糖果数n中去除这个超过的部分（即`limit + 1`），然后计算剩余糖果的分配方式，这就是`n + 2 - (limit + 1)`中的`(limit + 1)`的由来。
Stars and Bars定理通常用于计算将n个相同的物体分配到k个不同的箱子中的方式数。在无限制情况下，我们可以直接应用这个定理。但在有限制的情况下，如本题中每个小朋友获取的糖果数不能超过limit，我们需要使用容斥原理来调整计算方法。首先计算所有可能的分配方法（即无限制情况），然后逐步减去违反限制的情况（比如超过limit的情况），通过多次调整，最终得到满足所有条件的分配方法数。
在使用容斥原理时，必须确保`n + 2 - k * (limit + 1)`的值非负，因为负数情况下组合数没有意义。这就要求n必须足够大，至少大于等于`k * (limit + 1) - 2`。如果不满足这个条件，某些项就变得无效（即不能有负数的组合数）。这就对n提出了一个最小值的限制，确保所有计算项都有效，影响了算法的适用范围和正确性。
`C2`函数设计用于计算从n个不同物体中选择两个的组合数，即C(n, 2)。函数中有一个条件检查，如果n小于2，则直接返回0，因为从少于2个元素中选择2个是不可能的。这种处理确保了函数在所有输入情况下都能返回正确的组合数，避免了对负数或不合逻辑值的计算，保证了函数的稳健性。