首页使用C++解决问题:给你一个非负整数数组nums,你最初位于数组的第一个下标.数组中的每个元素代表你在该位置可以跳跃的最大长度.判断你是否能够到达最后一个下标,如果可以,返回true;否则,返回false.

使用C++解决问题:给你一个非负整数数组nums,你最初位于数组的第一个下标.数组中的每个元素代表你在该位置可以跳跃的最大长度.判断你是否能够到达最后一个下标,如果可以,返回true;否则,返回false.

时间: 2025-02-09 12:14:39 浏览: 44

这个问题通常被称为“跳台阶”或者“跳跃游戏”，可以用动态规划（Dynamic Programming）来解决。在 C++ 中，你可以通过维护一个变量记录当前能够达到的最远位置，并逐个考虑数组中的每个元素： 1. 首先，创建一个布尔变量 `canReach` 初始化为 `false`，表示默认无法到达最后一个下标。 2. 定义一个数组 `dp`，其大小等于 `nums` 的最大值加一，用于存储从当前位置到第 i 个位置是否可达的信息。初始化所有元素为 `false`，因为初始状态下只能到达第一个位置。 3. 然后遍历数组 `nums`，对于每个位置 `i`： - 如果 `dp[i]` 已经被设置为 `true`，说明我们已经找到了一条路径到达 `i`，并且当前位置可以从 `i-nums[i]` 跳到 `i`，所以我们检查 `dp[j]` 是否为 `true`，其中 `j = i-nums[i]`。如果 `dp[j]` 也为 `true`，则表明可以从 `j` 到达 `i` 再到最后一个下标，更新 `canReach` 为 `true`。 - 如果 `dp[i]` 为 `false` 并且 `i + nums[i] >= n-1`（n 为数组长度），这意味着我们可以直接跳到最后一个位置，所以将 `dp[i]` 设置为 `true`。 4. 遍历结束后，`canReach` 的状态就是能否到达最后一个下标的标志。如果是 `true`，返回 `true`；否则，返回 `false`。 ```cpp bool canJump(vector<int>& nums) { int n = nums.size(); if (n == 0 || nums[0] == 0) return false; dp.resize(n+1, false); dp[0] = true; for (int i = 1; i < n; ++i) { if (!dp[i]) continue; for (int j = i; j > 0 && j <= i + nums[i]; --j) { dp[j] = true; if (j == n - 1) return true; } } return dp[n]; } ```

阅读全文