Python|跳跃游戏

前言

贪心算法是指在对问题求解时，不从整体最优考虑，只是局部的最优考虑。所以贪心算法可能不能达到最优解，贪心算法也有正确的时候，求最小生成树的Prim算法和Kruskal算法都是漂亮的贪心算法。贪心算法的基本思路是从问题的某一个初始解出发一步一步地进行，根据某个优化测度，每一步都要确保能获得局部最优解。

问题描述

给定一个非负整数数组nums，你最初位于数组的第一个下标。数组中的每个元素代表你在该位置可以跳跃的最大长度。

判断你是否能够到达最后一个下标。

示例1：         示例2：

输入:nums = [2,3,1,1,4]    输入：nunms = [3,2,1,0,4]

输出：true          输出：false

解决方案

一般碰到能否走完，走的更远等题目，优先考虑贪心和动态规划两种方式，此题在这里讲的贪心，贪心算法更适合这一道题。示例1：此题的意思是当从数组下标为0的位置开始，下标为0的位置上的元素为2就可以跳一次或两次，如果跳一次就会跳到下标为1的位置，1位置的元素为3，那么现在可以跳跃1次2次3次，不管跳几次最终都能达到终点；如果跳两次，也可以到达终点。示例2：当从下标为0的位置开始跳，可以跳1次或2次或3次，但不管跳几次都会跳到元素0的位置，然后就跳不动了，就不能跳到终点。通过分析发现凡是数组中不含0的数组都可以跳到最后一个元素，如果数组中含0，那么就不能跳到最后一个元素。从下图可以清楚的看到过程。

红色代表起始跳2次，蓝色代表起始跳1次，跳的次数小于等于该位置的元素大小。

结语

此题运用贪心法就比较容易理解，就容易理解题目意思。可能还有更简单的算法，后期我会进一步研究。

实习编辑：衡辉

稿件来源：深度学习与文旅应用实验室（DLETA）