当我们看到这类题目时,首先要联想到贪心:针对一组数据,我们定义了期望值,限制值,希望从中选出几个数据,在满足限制值的条件下,期望值最大.
关键点就在于:每次在选择当前情况下,如果对期望值贡献一样的情况下,我们使用选择那个对期望值贡献最多的那个.
比如0,1背包问题. 限制值就是w kg, 期望值就是背包里所有物品的总价值最大,而贪心思想每次向背包里放1kg物品时,我们始终选择那个最贵的.
题号 | 题目链接 | 答案链接 | 难度 | 完成度 |
---|---|---|---|---|
55 | 跳跃游戏 | jump_game | medium | ✅ |
134 | 加油站 | gas_station | medium | ✅ |
455 | 分发饼干 | -- | ✨ | ❌ |
860 | 柠檬水找零 | -- | ✨ | ❌ |
874 | 模拟行走机器人 | -- | ✨ | ❌ |