2928. Distribute Candies Among Children I

,

Math

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
    public int distributeCandies(int n, int limit) {
        int count = 0;
        for (int i = 0; i <= Math.min(n, limit); i++) {
            if (n - i > 2 * limit) {
                continue;
            }
            count += Math.min(n - i, limit) - Math.max(n - i - limit, 0) + 1;
        }
        return count;
    }
}

DP

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution {
    public int distributeCandies(int n, int limit) {
        int[][] dp = new int[n + 1][4];
        dp[0][0] = 1; // 0 颗糖果分给 0 个小朋友的方案数为 1

        // i 颗糖果分给 0 个小朋友的方案数为 0
        for (int i = 1; i < dp.length; i++) {
            dp[i][0] = 0;
        }
        // 0 颗糖果分给 j 个小朋友的方案数为 1
        for (int j = 1; j < 4; j++) {
            dp[0][j] = 1;
        }

        for (int i = 1; i < dp.length; i++) {
            for (int j = 1; j < dp[i].length; j++) {
                for (int k = 0; k <= Math.min(i, limit); k++) {
                    dp[i][j] += dp[i - k][j - 1];
                }
            }
        }

        return dp[n][3];
    }
}

References

2928. Distribute Candies Among Children I