前言
新的一年，好好学习
正文
问题来源
本问题来自leetcode上的55题。
问题描述
给定一个非负整数数组，你最初位于数组的第一个位置。
数组中的每个元素代表你在该位置可以跳跃的最大长度。
判断你是否能够到达最后一个位置。
示例 1:
输入: [2,3,1,1,4]
输出: true
解释: 从位置 0 到 1 跳 1 步, 然后跳 3 步到达最后一个位置。
示例 2:
输入: [3,2,1,0,4]
输出: false
解释: 无论怎样，你总会到达索引为 3 的位置。但该位置的最大跳跃长度是 0 ， 所以你永远不可能到达最后一个位置。
分析：
回溯法有“通用解题法”之称。可以说是暴力做法。做题时没有想到更好的方法。
func canJump(nums []int) bool {
return backtrack(nums, 0)
}
func backtrack(nums []int,index int) bool {
if index == len(nums) -1 {
return true
} else if index > len(nums) - 1 {
return false
}
for i := nums[index]; i > 0; i-- {
if backtrack(nums, index+i) {
return true
}
}
return false
}
不幸的是还有最后一个测试用例超时了。算法本身应该是没什么问题的，主要是时间效率太低。
本题可采用贪心算法。（参考别人）
贪心算法（又称贪婪算法）是指，在对问题求解时，总是做出在当前看来最好的选择。也就是说，不从整体最优上加以考虑，他所作出的是在某种意义上的局部最优解。贪心算法和动态规划算法都是由局部最优导出全局最优，这里不得不比较下二者的区别
贪心算法： 1.贪心算法中，作出的每步贪心决策都无法改变，因为贪心策略是由上一步的最优解推导下一步的最优解，而上一部之前的最优解则不作保留。 2.由（1）中的介绍，可以知道贪心法正确的条件是：每一步的最优解一定包含上一步的最优解
动态规划算法： 1.全局最优解中一定包含某个局部最优解，但不一定包含前一个局部最优解，因此需要记录之前的所有最优解 2.动态规划的关键是状态转移方程，即如何由以求出的局部最优解来推导全局最优解 3.边界条件：即最简单的，可以直接得出的局部最优解
本题用一个数 reach 表示能到达的最远下标，一步步走下去，如果发现在 reach 范围之内某处能达到的范围大于 reach，那么我们就用更大的范围来替换掉原先的 reach，这样一个局部的最优贪心策略，在全局看来也是最优的，因为 局部能够到达的最大范围也是全局能够到达的最大范围：
func canJump(nums []int) bool {
reach := nums[0]
for i := 0; i < len(nums) && i <= reach; i++ {
if nums[i] + i > reach {
reach = nums[i] + i
}
}
return reach >= len(nums) - 1
}
总结：
勤思考。
结语
不管怎么样好好加油。
