自学 C++ 第 7 课 跳跃游戏 c++ 有趣的跳跃

跳跃游戏规则描述：先给定一个非负整数数组nums，例如 [4,4,0,2,3,3,1,2,4,2]，假定一台机器人要从nums[0]起跳，num[0]元素的值表示能跳跃的最大距离，也就是说，机器人第一次可跳跃到（4,0,2,3）中任意位置，第二次跳跃从第一次跳跃的落脚点起跳，可跳跃的最大距离是第一次跳跃的落脚点元素值。如果落脚点元素的值为0，表示无法跳跃。问，机器人针对一个给定数组（假设有n个元素），从nums[0]到nums[n-1]，最少需要跳跃几次？并标记出每次跳跃落脚点的坐标。

跳跃游戏需要每次做出选择时，都要选择下一次能够有更多选择或者更远距离的位置，每一次选择都是最优选择，最后累积出的结果也是最优的解。完成跳跃游戏的程序和算法很多，如何分析、推导其过程以及所有可能情况，通过目前所学的有限编程知识完成上述功能？

分析第一次跳跃过程，从nums[0]（nums[0]≠0）起跳，首先判断nums[0+1]到nums[0+nums[0]]区间内各元素能达到的最大边界 maxpos1 = j+nums[0+j]，j 值范围为1到nums[0]，并获得第一次跳跃落脚点的坐标 indexx1。数组nums为[4,4,0,2,3,3,1,2,4,2]时，第一次跳跃每个可选落脚点所能达到的最大边界maxpos1分别为 1+4=5；2+0=2 （0 无法跳跃）；3+2=5；4+3=7；所以最优选择的落脚点坐标 indexx1=4。如果数组nums变为[4,4,0,4,3,3,1,2,4,2]，那么会出现两个最大值，对于跳跃过程中出现的多个解，为了方便程序处理，皆取最后一个满足maxpos1的元素坐标。

第二跳跃，是从nums[indexx1]起跳，判断nums[indexx1+1]到nums[indexx1+nums[indexx1]]区间内各元素能达到的最大边界maxpos2 = j+nums[indexx1+j]，j值范围为1到nums[indexx1]，并获得第一次跳跃落脚点的坐标 indexx2。对于数组[4,4,0,2,3,3,1,2,4,2]，从nums[4]起跳，第二次跳跃每个可选落脚点所能达到的最大边界maxpos2分别为1+3=4；2+1=3；3+2=5；所以最优选择的落脚点坐标 indexx2=indexx1+3=7。

第三次跳跃以此类推，通过判断indexx2+maxpos3的值是否大于等于9来确定，下一跳跃是否能够到达nums[9]，数组[4,4,0,2,3,3,1,2,4,2]的indexx2+maxpos3等于9，所以最少需要3次跳跃到达终点。

对于非零数组nums，还存在几种特殊情况：

一是nums[0]等于0，即无法起跳，例如[0,1,2,3,1]；

二是nums[0]大于或等于n-1，即一次跳跃即可到达终点，例如[5,2,3,0,1,6]；

三是所有选择的最终落脚点皆为0，即无法继续跳跃，例如[3,2,1,0,1,2,3]或[3,3,2,1,0,1]

根据上述分析，除了sums[]数组，每次跳跃后可能达到的最大边界和落脚点坐标分别用两个数组maxpos[]和indexx[]，使用vector声明数组并默认初始化为0。

知识点：

? fmax(x,y); 返回两个参数中的最大值，该函数定义于<cmath>标准库头文件中。英文对照说明：fmax() function is a library function of cmath header, it is used to find the maximum value of the given numbers, it accepts two number and returns the larger one.

? || 是逻辑或运算符，只要运算符||两边表达式有一个为ture，运算结果就为ture，判断语句执行；只有运算符||两边表达式均为false，运算结果才是false，判断语句不执行；如果前面一个表达式为true，那么就不会再执行和判断后面的表达式。

? break作用是结束跳出循环体，直接执行循环体以外的下一行语句。在单个循环语句中，break作用是跳出该循环语句；在嵌套循环中，break作用是跳出最近的循环，并且不影响外层的循环。

自学 C++ 第 1 课 数字大小排序

自学 C++ 第 2 课 数组包含关系

自学 C++ 第 3 课 正整数反序输出

自学 C++ 第 4 课 计算体积及表面积

自学 C++ 第 5 课 杨辉三角

自学 C++ 第 6 课 二维数组找最值