Leetcode45. 跳跃游戏 II

Every day a Leetcode

题目来源：45. 跳跃游戏 II

解法1：动态规划 + 贪心

定义 dp[i] 表示到达 i 的最少跳数。

因为题目保证能跳动终点，只要前面的点（j < i）能跳到 i 点就更新最小值。

代码：

class Solution
{
public:int jump(vector<int> &nums){int n = nums.size();// dp[i] 表示到达 i 的最少跳数vector<int> dp(n, INT_MAX);// 初始化dp[0] = 0;// 状态转移for (int i = 1; i < n; i++){for (int j = 0; j < i; j++)if (j + nums[j] >= i)dp[i] = min(dp[i], dp[j] + 1);}return dp[n - 1];}
};

优化：找到第一个能跳到 i 的点 last，使用点 last 更新 dp[i]。

// 动态规划class Solution
{
public:int jump(vector<int> &nums){int n = nums.size();// dp[i] 表示到达 i 的最少跳数vector<int> dp(n, INT_MAX);// 初始化dp[0] = 0;// 状态转移for (int i = 1, last = 0; i < n; i++){// 找到第一个能跳到 i 的点 lastwhile (last < n && last + nums[last] < i)last++;// 使用点 last 更新 dp[i]dp[i] = min(dp[i], dp[last] + 1);}return dp[n - 1];}
};

结果：

复杂度分析：

时间复杂度：O(n)，其中 n 是数组 nums 的长度。

空间复杂度：O(n)，其中 n 是数组 nums 的长度。

解法2：贪心

正向查找可到达的最大位置。

代码：

class Solution
{
public:int jump(vector<int> &nums){int max_far = 0; // 目前能跳到的最远位置int step = 0;    // 跳跃次数int end = 0;     // 上次跳跃可达范围右边界（下次的最右起跳点）for (int i = 0; i < nums.size() - 1; i++){max_far = max(max_far, i + nums[i]);// 到达上次跳跃能到达的右边界了if (i == end){end = max_far; // 目前能跳到的最远位置变成了下次的最右起跳点step++;        // 进入下一次跳跃}}return step;}
};

反向查找出发位置。

代码：

class Solution
{
public:int jump(vector<int> &nums){int max_far = 0; // 目前能跳到的最远位置int step = 0;    // 跳跃次数int end = 0;     // 上次跳跃可达范围右边界（下次的最右起跳点）for (int i = 0; i < nums.size() - 1; i++){max_far = max(max_far, i + nums[i]);// 到达上次跳跃能到达的右边界了if (i == end){end = max_far; // 目前能跳到的最远位置变成了下次的最右起跳点step++;        // 进入下一次跳跃}}return step;}
};

结果：

复杂度分析：

时间复杂度：O(n)，其中 n 是数组 nums 的长度。

空间复杂度：O(1)。