618 字
3 分钟
55. 跳跃游戏
55. 跳跃游戏
给你一个非负整数数组 nums ，你最初位于数组的 第一个下标 。数组中的每个元素代表你在该位置可以跳跃的最大长度。
判断你是否能够到达最后一个下标，如果可以，返回 true ；否则，返回 false 。
示例
示例 1：
输入：nums = [2,3,1,1,4]输出：true解释：可以先跳 1 步，从下标 0 到达下标 1, 然后再从下标 1 跳 3 步到达最后一个下标。示例 2：
输入：nums = [3,2,1,0,4]输出：false解释：无论怎样，总会到达下标为 3 的位置。但该下标的最大跳跃长度是 0 ， 所以永远不可能到达最后一个下标。思路
采用动态规划的思路，每个位置的最大可达距离可以通过计算当前的位置的可达距离和上一个位置的最大可达距离来更新（最大可达距离具有传递性）。
- 定义一个数组
dp，其中dp[i]表示到达位置i的最大可达距离。 - 初始化
dp[0] = nums[0]，表示从起点位置可以到达的最远距离。 - 当前位置可以到达的最远位置 = max(上个位置的最远位置，当前位置 + 最大移动距离)
- 如果从上一个状态无法到达当前位置，则返回 false。
- 如果最后能达到末尾
n-1返回 true。
代码
class Solution {public: bool canJump(vector<int>& nums) { int n = nums.size(); vector<int> dp(n, 0); dp[0] = nums[0]; for(int i = 1; i < n; i++){ if(i > dp[i - 1]) return false; // 如果当前位置可以到达 // 当前能够到达的最远位置 = max(上个位置的最远位置，(当前位置 + 最大移动距离)) dp[i] = max(dp[i - 1], i + nums[i]); } // 如果最后能达到末尾返回true return dp[n - 1] >= n - 1; }};优化
由于动态规划数组中，每一次更新数据只依赖于前一个位置的状态，因此可以将空间复杂度从 O(n) 降低到 O(1)。
class Solution {public: bool canJump(vector<int>& nums) { int n = nums.size(); int dp = nums[0]; for(int i = 1; i < n; i++){ if(i > dp) return false; // 如果当前位置可以到达 // 当前能够到达的最远位置 = max(上个位置的最远位置，(当前位置 + 最大移动距离)) dp = max(dp, i + nums[i]); } // 如果最后能达到末尾返回true return dp >= n - 1; }};