题解 | #跳跃游戏(一)# ✅✅✅贪心解法、动态规划解法

关键词：贪心算法、动态规划

动态规划解法：

核心思想：动态规划解决，维护一个dp数组，其中dp[i]表示到达索引i时能到达的最远距离。

解题步骤：

1. 创建大小为n的dp数组，初始值设为-1，表示这些位置不可达。
2. 初始化状态，设置dp[0]为nums[0]，即从起始位置能到达的最远距离。
3. 对于每一个索引i（从1到n-1）:如果dp[i-1]小于i，则当前位置不可达，直接设置dp[i]为-1。否则，更新dp[i]为max(dp[i-1], i + nums[i])，表示当前最远可达距离。
4. 最后检查dp[n-1]是否为-1，如不是则说明最后一个位置可达。

复杂度：时间复杂度O(n)，空间复杂度O(n)。

#include <iostream>
#include <vector>
using namespace std;

int main() {
    int n;
    cin >> n;
    vector<int> nums(n), dp(n, -1);
    for (int i = 0; i < n; ++i) cin >> nums[i];

    dp[0] = nums[0];
    for (int i = 1; i < n; ++i) {
        if (dp[i - 1] < i) dp[i] = -1;
        else dp[i] = max(dp[i - 1], i + nums[i]);
    }

    cout << (dp[n-1] != -1 ? "true" : "false") << endl;
    return 0;
}

贪心解法：

核心思想：维护一个变量maxReach，表示当前能到达的最远位置。

解题步骤：

1. 初始化maxReach为nums[0]，表示从起始位置能到达的最远距离。
2. 遍历数组（从索引1到n-1）：如果当前索引i大于maxReach，则无法到达当前位置，输出false并结束程序。更新maxReach为max(maxReach, i + nums[i])，表示当前最远可达距离。
3. 若能够遍历完整个数组，输出true。

复杂度：时间复杂度O(n)，空间复杂度O(n)。

#include <iostream>
#include <vector>
using namespace std;

int main() {
    int n;
    cin >> n;
    vector<int> nums(n);
    for (int i = 0; i < n; ++i) cin >> nums[i];

    int maxReach = nums[0];
    for (int i = 1; i < n; ++i) {
        if(i>maxReach){
            cout << "false";
            return 0;
        }
        maxReach = max(maxReach, i + nums[i]);
    }
    cout << "true";
    return 0;
}