如何运用贪心思想玩跳跃游戏
原创约 2309 字
本文讲解的例题
| LeetCode | 力扣 | 难度 |
|---|---|---|
| 45. Jump Game II | 45. 跳跃游戏 II | 🟠 |
| 55. Jump Game | 55. 跳跃游戏 | 🟠 |
经常有读者在后台问，动态规划和贪心算法到底有啥关系。我们之前的文章 贪心算法之区间调度问题 就说过一个常见的时间区间调度的贪心算法问题。
说白了，贪心算法可以理解为一种特殊的动态规划问题，拥有一些更特殊的性质，可以进一步降低动态规划算法的时间复杂度。那么这篇文章，就讲 LeetCode 上两道经典的贪心算法：跳跃游戏 I 和跳跃游戏 II。
我们可以对这两道题分别使用动态规划算法和贪心算法进行求解，通过实践，你就能更深刻地理解贪心和动规的区别和联系了。