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^2 * children)$
- 空间复杂度：$O(money * children)$
先每个人分配一块钱，保证题目约束”每个人“都需要分到。
接下来，我们再贪心地令尽可能多的人分到 8 块钱，记为 x 人能分到 8 元。
最后检查一下是否满足题目的约束：
- 不能有人分到 4 元
- 不能剩余有钱
如果有人分到 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 啦。大家也可以关注我的公众号《力扣加加》带你啃下算法这块硬骨头。
关注公众号力扣加加，努力用清晰直白的语言还原解题思路，并且有大量图解，手把手教你识别套路，高效刷题。
