# 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 啦。大家也可以关注我的公众号《力扣加加》带你啃下算法这块硬骨头。
关注公众号力扣加加，努力用清晰直白的语言还原解题思路，并且有大量图解，手把手教你识别套路，高效刷题。
