2591. 将钱分给最多的儿童

题目地址(2591. 将钱分给最多的儿童)

https://leetcode.cn/problems/distribute-money-to-maximum-children/

题目描述

给你一个整数 money ，表示你总共有的钱数（单位为美元）和另一个整数 children ，表示你要将钱分配给多少个儿童。

你需要按照如下规则分配：

所有的钱都必须被分配。
每个儿童至少获得 1 美元。
没有人获得 4 美元。

请你按照上述规则分配金钱，并返回 最多 有多少个儿童获得 恰好 8 美元。如果没有任何分配方案，返回 -1 。

 

示例 1：

输入：money = 20, children = 3
输出：1
解释：
最多获得 8 美元的儿童数为 1 。一种分配方案为：
- 给第一个儿童分配 8 美元。
- 给第二个儿童分配 9 美元。
- 给第三个儿童分配 3 美元。
没有分配方案能让获得 8 美元的儿童数超过 1 。


示例 2：

输入：money = 16, children = 2
输出：2
解释：每个儿童都可以获得 8 美元。


 

提示：

1 <= money <= 200
2 <= children <= 30

前置知识

• 动态规划

• 脑筋急转弯

公司

• 暂无

动态规划（超时）

思路

这个或许是力扣最难的简单题了，很多大佬都没有一次 AC。这是某一次周赛的第一道题目，第一道题目就是俗称的打卡题，不过似乎很多人都没有通过就是了。

周赛讨论地址：https://leetcode.cn/circle/discuss/Gx4OWK/

即使使用动态规划来解决， 很多语言也无法通过，比如 Python，从这一点看就已经比很多中等难度的难了。

而且脑筋急转弯这种东西，想不到就很烦，不太适合作为简单题。

定义 dp[i][j] 表示将 i 元分配给 j 个人，最多有 dp[i][j] 个人分到 8 元。

初始化 dp 所有项目都是无限小，边界 dp[0][0] = 0。接下来枚举 i 和 j 的组合并进行转移， 转移方程是 dp[i][j] = max(dp[i][j], int(k == 8) + dp[i - k][j - 1])，其中 k 为 分配给当前儿童的钱数，由于只能分配 1 到 money 元，直接枚举 k 进行转移即可，如果 k == 8，那么就多了一个分配 8 元的人， 加 1 即可。

代码我写了记忆化递归和自底向上的动态规划，可惜的是都无法通过。

代码

• 语言支持：Python3

Python3 Code:

class Solution:
    def distMoney(self, money: int, children: int) -> int:
        # @cache
        # def dp(money, children):
        #     if children == 0:
        #         if money == 0: return 0
        #         return -inf
        #     if money == 0: return -inf
        #     ans = -inf
        #     for i in range(1, money+1):
        #         if i == 4: continue
        #         ans = max(ans, int(i == 8) + dp(money - i, children - 1))
        #     return ans
        # ans = dp(money, children)
        # if ans == -inf: return -1
        # return ans
        if money < children: return -1
        dp = [[-inf] * (children+1) for _ in range(money+1)]
        dp[0][0] = 0
        for i in range(money+1):
            for j in range(1, children+1):
                for k in range(1, i+1):
                    if k == 4: continue
                    dp[i][j] = max(dp[i][j], int(k == 8) + dp[i - k][j - 1])
        return -1 if dp[-1][-1] == -inf else dp[-1][-1]

复杂度分析

由于状态总数是 money * children，状态转移的时间是 $O(money)$，因此：

• 时间复杂度：$O(money^2 * children)$

• 空间复杂度：$O(money * children)$

贪心+脑筋急转弯

思路

先每个人分配一块钱，保证题目约束”每个人“都需要分到。

接下来，我们再贪心地令尽可能多的人分到 8 块钱，记为 x 人能分到 8 元。

最后检查一下是否满足题目的约束：

1. 不能有人分到 4 元

2. 不能剩余有钱

如果有人分到 4 元，那么我们只能将前面的 x 人多分一点或者少分一点，使得满足条件，不管怎么样，我们至少需要将 x 减去 1。

如果有剩余的钱也是同样的道理。

关键点

• 先每个人分配一块钱，保证题目约束”每个人“都需要分到。

• 贪心

代码

• 语言支持：Python3

Python3 Code:

class Solution:
    def distMoney(self, money: int, children: int) -> int:
        money -= children  # 每人至少 1 美元
        if money < 0: return -1
        ans = min(money // 7, children)  # 初步分配，让尽量多的人分到 8 美元
        money -= ans * 7
        children -= ans
        # children == 0 and money：必须找一个前面分了 8 美元的人，分配完剩余的钱
        # children == 1 and money == 3：不能有人恰好分到 4 美元
        if children == 0 and money or \
           children == 1 and money == 3:
            ans -= 1
        return ans

复杂度分析

• 时间复杂度：$O(1)$

• 空间复杂度：$O(1)$

此题解由 力扣刷题插件 自动生成。

力扣的小伙伴可以关注我，这样就会第一时间收到我的动态啦~

以上就是本文的全部内容了。大家对此有何看法，欢迎给我留言，我有时间都会一一查看回答。更多算法套路可以访问我的 LeetCode 题解仓库：https://github.com/azl397985856/leetcode 。 目前已经 40K star 啦。大家也可以关注我的公众号《力扣加加》带你啃下算法这块硬骨头。

关注公众号力扣加加，努力用清晰直白的语言还原解题思路，并且有大量图解，手把手教你识别套路，高效刷题。