# 2591. 将钱分给最多的儿童
### 题目地址(2591. 将钱分给最多的儿童)
### 题目描述
```
给你一个整数 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。这是某一次周赛的第一道题目，第一道题目就是俗称的打卡题，不过似乎很多人都没有通过就是了。
周赛讨论地址：
即使使用动态规划来解决， 很多语言也无法通过，比如 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:
```python
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:
```python
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)$
> 此题解由 [力扣刷题插件](https://leetcode-pp.github.io/leetcode-cheat/?tab=solution-template) 自动生成。
力扣的小伙伴可以[关注我](https://leetcode-cn.com/u/fe-lucifer/)，这样就会第一时间收到我的动态啦\~
以上就是本文的全部内容了。大家对此有何看法，欢迎给我留言，我有时间都会一一查看回答。更多算法套路可以访问我的 LeetCode 题解仓库： 。 目前已经 40K star 啦。大家也可以关注我的公众号《力扣加加》带你啃下算法这块硬骨头。
关注公众号力扣加加，努力用清晰直白的语言还原解题思路，并且有大量图解，手把手教你识别套路，高效刷题。
---
# Agent Instructions: Querying This Documentation
If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.
Perform an HTTP GET request on the current page URL with the `ask` query parameter:
```
GET https://leetcode-solution-leetcode-pp.gitbook.io/leetcode-solution/easy/2591.distribute-money-to-maximum-children.md?ask=
```
The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.
Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.