知识点

LeetCode算法

1. LeetCode算法

   1. 55.【跳跃游戏】

      解题思路：

      该题目虽然明面上没有求最值，但是可以转化一下题目：请问通过题目中的跳跃规则，最多能跳多远？如果能够越过最后一格，返回 true，否则返回 false。

      因此，该题目可以使用动态规划来做。

      同时，因为该题目满足贪心性质，因此贪心算法是更好的选择。

   2. 45.【跳跃游戏 II】

      解题思路：

      转化一下题目，保证一定可以跳到最后一格，请问你最少要跳多少次，才能跳过去。

      第一个想到的，就是动态规划思路。

      动态规划思路如下：

      1、确定dp数组。dp数组定义为：dp[i]为跳到i元素需要的最少跳跃数。

      2、确定base case。base case：每个i位置需要的跳跃数为i下。

      3、确定状态转移方程。

      但是，这不是最好的解法。该题目有贪心性质，可以使用贪心算法来做。

      for 循环中会陷入递归计算子问题，但是，需要计算出每一个子问题的结果，然后求最值吗？其实不需要，我们只需要判断哪个选择所在的元素跳跃的距离更大即可，例如[3, 1, 1, 4, 2, 2]中，从0索引开始跳显然应该跳到索引3，因为nums[3]的可跳跃区域比其他的更大。

      我们不需要计算出所有选择的具体结果然后比较求最值，而只需要做出那个最有「潜力」，看起来最优的选择即可

      上述的，就是贪心算法的思路。