2928.给小朋友们分糖果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

思路

简单题数据范围小，直接暴力求解。别看不起暴力解法，真想用其它方法求解并不简单。

这道题要求解n个球装到三个容量为limit的盒子里总共有多少种分配方案。如果容量没有限制很简单直接从n+(3-1)个位置中选2个即可。

不暴力求解的话就要考虑动态规划了。// todo

代码

/**
 * @date 2024-06-01 15:59
 */
public class DistributeCandies2928 {
    public int distributeCandies(int n, int limit) {
        int res = 0;
        // 为第一个小朋友分配有0~limit种可能
        for (int i = 0; i <= limit; i++) {
            // 这时为第二个小朋友可以有n - i种可能，这里不要忘了不能超过limit
            for (int j = 0; j <= Math.min(limit, n - i); j++) {
                // 第三个小朋友，获取剩下的糖果，但不能超过limit
                if(n - i - j <= limit){
                    res++;
                }
            }
        }
        return res;
    }
}

性能