引言这两道题属于贪心经典题型核心都是基于数组元素代表最大跳跃长度两道题题干相近但目标不同一题判断是否可达终点一题求到达终点的最小跳跃次数。基础篇跳跃游戏 I约束起始在下标 0nums [i] 代表当前位置向后最大跳跃距离判断是否能够到达最后一个下标。思路 1正向贪心方法维护max_reach记录当前能跳到的最远下标。遍历数组不断更新最远可达位置若遍历到某个位置i max_reach说明无法到达该位置直接返回 false若max_reach n-1可提前返回 true。复杂度时间 (O(n))空间 (O(1))class Solution { public: bool canJump(vectorint nums) { int max_reach 0; int n nums.size(); for(int i 0; i n; i){ if(i max_reach) return false; // 当前位置不可达 max_reach max(max_reach, i nums[i]); if(max_reach n-1) return true; } return true; } };思路 2动态规划方法dp[i]表示下标i是否可达。初始化dp[0]true遍历每个位置如果当前位置可达则标记它后续能跳到的位置全部可达。复杂度时间 (O(n^2))空间 (O(n))大数据会超时仅理解用。bool canJump(vectorint nums) { int n nums.size(); vectorbool dp(n, false); dp[0] true; for(int i0;in;i){ if(!dp[i]) continue; for(int j1;jnums[i];j){ if(ij n-1) return true; dp[ij] true; } } return dp[n-1]; }进阶篇跳跃游戏 II约束起始在下标 0nums [i] 代表当前位置向后最大跳跃距离保证一定可以到达终点求到达最后下标的最小跳跃次数。思路 1区间贪心方法维护 3 个变量当前区间边界end、全局最远可达位置max_reach、跳跃次数step。遍历到区间边界end时代表必须起跳一次更新边界为全局最远位置。复杂度时间 (O(n))空间 (O(1))class Solution { public: int jump(vectorint nums) { int n nums.size(); if(n 1) return 0; int step 0; int end 0; int max_reach 0; for(int i 0; i n-1; i){ max_reach max(max_reach, i nums[i]); if(i end){ // 走到区间边界必须起跳 step; end max_reach; } } return step; } };思路 2反向贪心方法从终点向前搜索找到最靠左的、能够跳到当前终点的位置更新终点为此位置跳跃次数 1直到终点回到下标 0。复杂度时间 (O(n^2))空间 (O(1))int jump(vectorint nums) { int pos nums.size()-1; int step 0; while(pos 0){ // 从左往右找第一个能跳到pos的下标 for(int i0; ipos; i){ if(i nums[i] pos){ pos i; step; break; } } } return step; }总结题号题目约束最优解法核心变量55跳跃游戏 I判断能否到达终点正向贪心max_reach45跳跃游戏 II求最小跳跃次数保证可达区间贪心end、max_reach、stepI只关心能不能到达 → 贪心维护最远可达下标II求最少跳跃次数 → 区间贪心到达区间边界才计数