Skip to content

Latest commit

 

History

History
187 lines (115 loc) · 5.62 KB

2591.distribute-money-to-maximum-children.md

File metadata and controls

187 lines (115 loc) · 5.62 KB

题目地址(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 啦。大家也可以关注我的公众号《力扣加加》带你啃下算法这块硬骨头。

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