双周赛117

双周赛117

好久没打比赛了，感觉还是没有系统地刷题，导致很多题目有思路但是不知道怎么写。所以这场双周赛就详细说说~

T1. 2928. 给小朋友们分糖果 I

1. 题目说明

给你两个正整数 n 和 limit 。

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

示例 1：

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

提示1：

1. 当n和limit的量较小时：

• 1 <= n <= 50

• 1 <= limit <= 50

2. 当n和limit的量较大时：

• 1 <= n <= 106

• 1 <= limit <= 106

2. 解答分析

1. 数学方法（通用）：

• 给定总共的糖果数量n，每人分得的糖果数量存在限制limit。如果是要分给三个人，其实就是在两个人当中进行判断，剩余的糖果分给第三个人就行。比如说A、B、C三个人，我们从后向前按照人进行分析：
  • 对于C而言，单独的一个人的分得糖果数为[0,limit]，不超过右边界的值
  • 对于B而言，此时假设选取的数量为i，i的取值范围的左边界应该是最小值，我们知道如果A、C两个人数量都选择limit，此时的左边界在[0,n-2*limit]中选取最大值；对于右边界而言，当A、C都取不到最大的Limit的时候，剩余的量应该是[limit,n],这里我们选取的是较小值，如果选取的是最大值的话，会导致和左边界重合。
  • 对于A而言，由于已经对B和C进行了分类，类似与上述的B，左边界为[0,n-i-limit]中的较大值，右边界为[limit,n-i]的较小值。此时C的选择的方案数即为最后总方案数，需要注意的是，如果此时左边界和右边界重合的时候，也存在一种方案，此时的C为0而已。

2. 记忆化搜索（递归量小）：

• 对于每次递归拆分而言，但是利用HashMap记录当前的键值对。

• 利用dfs对糖果数进行操作，记录剩余的数量rest和当前的轮数rank,但是每出现新的轮数+”，“+糖果数的时候，此时通过记忆化搜索进行减少递归的操作，直接从HashMap的数组堆的结构中寻找存储的值即可。

  ​

3. 具体代码

//1. 数学方式：
class Solution{
    public long distributeCandies(int n,int limit){
        // 特例判断，当此时的超过全体取limit的时候，也就是糖果数量存在冗余的情况
        if(limit*3<n){
            return 0;
        }
        long sum=0;
        // 对B进行判断
        for(int i=Math.max(0,n-2*limit);i<=Math.min(limit,n);i++){
            sum+=(Math.min(limit,n-i)-Math.max(0,n-i-limit)+1);
        }
        return sum;
    }
}

class Solution {
    public int distributeCandies(int n, int limit) {
        //记忆化搜索的思想
        Map<String,Integer>memo=new HashMap<>();
        return dfs(0,n,limit,memo);
    }
    private int dfs(int rank,int rest,int limit,Map<String,Integer>memo){
        if(rk==3){ //最后一轮的时候，此时仍然有剩余的话，返回1次，否则为0，注意递归需要关注的是cnt的值
            return rest==0?1:0;
        }
        String key=rank+","+rest; //按照轮数和剩余数进行匹配
        if(memo.containsKey(key)){
            return memo.get(key); //记忆化拿取
        }
        int cnt=0;
        for(int i=0;i<=limit;i++){
            if(rest<i){ //递归错误，跳出结构
                break;
            }
            cnt+=dfs(rk+1,rest-i,limit,memo); //递归，改变的是剩余量
        }
        memo.put(key,cnt); //记忆化记录
        return cnt;
    }
}