《灵珠觉醒：从零到算法金仙的C++修炼》卷三·天劫试炼（54）落宝金钱寻最优 - 跳跃游戏（贪心策略）
《灵珠觉醒：从零到算法金仙的C++修炼》卷三·天劫试炼（54）落宝金钱寻最优 - 跳跃游戏（贪心策略）
哪吒在数据修仙界中继续他的修炼之旅。这一次，他来到了一片神秘的落宝金钱谷，谷中有一条长长的石板路，每块石板上刻有数字，代表哪吒在此处可获得的灵力值。谷口有一块巨大的石碑，上面刻着一行文字：“欲破此谷，需以落宝金钱之力，寻最优跳跃路径，贪心策略显真身。”
哪吒定睛一看，石碑上还有一行小字：“数组[2, 3, 1, 1, 4]表示每块石板上的灵力值，哪吒从第一块石板出发，每次跳跃最远可跳至灵力值所指示的下一块石板，最终能否到达最后一块石板？”哪吒心中一动，他知道这是一道关于跳跃游戏的难题，需要通过贪心策略来找到最优跳跃路径。
暴力解法：落宝金钱的初次尝试
哪吒心想：“要判断能否到达最后一块石板，我可以逐个石板尝试跳跃。”他催动落宝金钱之力，从第一块石板开始，逐个石板跳跃，试图找到一条到达终点的路径。
bool canJump(vector<int>& nums) {
int n = nums.size();
vector<bool> dp(n, false);
dp[0] = true;
for (int i = 0; i < n; ++i) {
if (dp[i]) {
for (int j = 1; j <= nums[i]; ++j) {
if (i + j < n) {
dp[i + j] = true;
}
}
}
}
return dp[n - 1];
}
哪吒成功地判断了能否到达最后一块石板，但落宝金钱的光芒却黯淡了下来。他意识到，这种方法虽然可行，但效率低下，尤其是当石板数量很多时，灵力消耗巨大。
C++语法点
在C++中，跳跃游戏问题涉及到数组的遍历和贪心策略。以下是一些重要特性：
-
数组遍历：
- 使用
for循环遍历数组。 - 常用操作：
nums[i]：访问数组中的元素。
- 使用
-
贪心策略：
- 通过维护最远可达位置，避免逐个石板尝试。
高阶优化：贪心策略的智慧
哪吒元神中突然浮现金色铭文——「落宝金钱寻最优，贪心策略显真身」。他意识到，可以通过贪心策略优化跳跃游戏的判断过程。
哪吒决定使用贪心策略，维护一个最远可达位置maxReach，每次跳跃时更新maxReach，如果当前石板的索引超过maxReach，则无法继续跳跃。通过这种方式，他成功地判断了能否到达最后一块石板，而且灵力消耗大幅减少。
bool canJump(vector