《灵珠觉醒:从零到算法金仙的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