55. Jump Game

Given an array of non-negative integers, you are initially positioned at the first index of the array.

Each element in the array represents your maximum jump length at that position.

Determine if you are able to reach the last index.

Example 1:

Input: [2,3,1,1,4]
Output: true
Explanation: Jump 1 step from index 0 to 1, then 3 steps to the last index.

Example 2:

Input: [3,2,1,0,4]
Output: false
Explanation: You will always arrive at index 3 no matter what. Its maximum
             jump length is 0, which makes it impossible to reach the last index.

思路

题目大致意思：从数组首开始，每一步能跳的最远距离就是当前index的值，问能否达到数组末尾。

这里使用贪心算法来解:

• 只要能达到的最远距离大于数组末尾的index，则为true
• 当前index能达到的最远index是：i + nums[i]
• 如果当前index的值大于等于最大能达到的最大index，意味着碰到0了，如 [3,2,1,0,4], 则返回false

c++11

class Solution {
public:
    bool canJump(vector<int>& nums) {
        auto len = nums.size();
        if (len == 0) return false;
        for (int i = 0, reach_max = 0; i < len; i++) {
            reach_max = std::max(reach_max, i + nums[i]);
            if (reach_max >= len - 1) return true;
            else if (reach_max <= i) break;
        }
        return false;
    }
};

贪心算法

使用贪心算法，回顾一下贪心算法：

贪心算法是一种在每一步选择中都采取在当前状态下最好或最优（即最有利）的选择，从而希望导致结果是最好或最优的算法。

贪心算法在有最优子结构的问题中尤为有效。最优子结构的意思是局部最优解能决定全局最优解。简单地说，问题能够分解成子问题来解决，子问题的最优解能递推到最终问题的最优解。

贪心法可以解决一些最优化问题，如：求图中的最小生成树、求哈夫曼编码……对于其他问题，贪心法一般不能得到我们所要求的答案。

一旦一个问题可以通过贪心法来解决，那么贪心法一般是解决这个问题的最好办法。由于贪心法的高效性以及其所求得的答案比较接近最优结果，贪心法也可以用作辅助算法或者直接解决一些要求结果不特别精确的问题。

实现步骤：

• 建立数学模型来描述问题。
• 把求解的问题分成若干个子问题。
• 对每一子问题求解，得到子问题的局部最优解。
• 把子问题的解局部最优解合成原来解问题的一个解。

实现该算法的过程：

从问题的某一初始解出发；
while 能朝给定总目标前进一步 
    do，求出可行解的一个解元素；
最后，由所有解元素组合成问题的一个可行解。

和动态规划的区别：

贪心算法与动态规划的不同在于它对每个子问题的解决方案都做出选择，不能回退。动态规划则会保存以前的运算结果，并根据以前的结果对当前进行选择，有回退功能。