跳跃游戏问题的C语言高效解法问询：替代递归DP方案

问题回顾 #

给定一个整数数组，初始位置为数组的第一个下标，数组中的每个元素代表当前位置的最大跳跃长度。若能到达最后一个下标则返回true，否则返回false。

示例1：

输入：array = [2,3,1,1,4]
输出：true
解释：从下标0跳1步到下标1，再跳3步到达最后一个下标。

示例2：

输入：array = [3,2,1,0,4]
输出：false
解释：无论如何都会到达下标3，其最大跳跃长度为0，无法到达最后一个下标。

你当前使用递归加记忆化DP的方法时间效率较低，以下提供贪心算法的实现，时间复杂度O(n)，空间复杂度O(1)，是该问题的最优解法。

贪心算法思路 #

核心逻辑是维护一个变量max_reach，记录当前能到达的最远下标：

• 遍历数组中的每个位置i：
  1. 如果当前位置i超过了max_reach，说明无法到达该位置，直接返回false。
  2. 更新max_reach为max(max_reach, i + nums[i])，即当前位置能跳到的最远位置和之前的最远位置取较大值。
  3. 如果max_reach已经大于等于数组最后一个下标，说明可以到达终点，直接返回true。

C语言实现代码 #

bool canJump(int* nums, int numsSize) {
    int max_reach = 0;
    for (int i = 0; i < numsSize; i++) {
        // 当前位置无法到达，直接返回false
        if (i > max_reach) {
            return false;
        }
        // 更新能到达的最远位置
        if (i + nums[i] > max_reach) {
            max_reach = i + nums[i];
        }
        // 已经能到达终点，提前返回true
        if (max_reach >= numsSize - 1) {
            return true;
        }
    }
    // 遍历结束后检查是否能到达终点
    return max_reach >= numsSize - 1;
}

效率对比 #

• 你的递归记忆化DP方法：时间复杂度O(n²)（最坏情况下每个位置都要遍历所有可能的跳跃），空间复杂度O(n)（需要DP数组和递归栈空间）。
• 贪心算法：时间复杂度O(n)（仅遍历一次数组），空间复杂度O(1)（仅用一个变量记录最远位置），避免了递归的栈开销和内存分配，在大数据量下效率提升明显。

内容的提问来源于stack exchange，提问作者Mohamed Afsal