问题描述 给你一个整数数组。您最初位于数组的第一个索引处，数组中的每个元素代表您在该位置的最大跳跃长度。
如果可以到达最后一个索引，则返回 true，否则返回 false。
示例1：
输入：数组 = [2,3,1,1,4] 输出：真 解释：从索引 0 跳 1 步到 1，然后跳 3 步到最后一个索引。 示例2：
输入：数组 = [3,2,1,0,4] 输出：假 说明：无论如何，你总是会到达索引 3。它的最大跳转长度为0，这使得无法到达最后一个索引。
问题 （链接：https://leetcode.com/problems/jump-game/） 我使用递归来解决这个问题，但这会花费更多时间。那么，有什么方法可以用任何其他逻辑在 C 编程中有效地解决这个问题。 我的节目
bool isValid(int i,int* arr, int n, int* dp){
if(i==n-1)return true;
else if(i>=n)return false;
else if(dp[i]!=-1)return dp[i]==1?true:false;
for(int jump=1;jump<=arr[i];jump++){
if(isValid(i+jump, arr, n,dp)){
dp[i]=1;
return true;
}
}
return dp[i]=0;
}
bool canJump(int* nums, int numsSize) {
int* dp = (int*)malloc(sizeof(int)*numsSize);
for(int i=0;i<numsSize;i++)dp[i]=-1;
return isValid(0, nums, numsSize, dp);
}
我使用递归来解决这个问题，但这会花费更多时间。那么，有什么方法可以用任何其他逻辑在 C 编程中有效地解决这个问题。
由于你只能向前跳跃，所以这可以非常有效地完成。
遍历数组一次。如果当前索引大于最大可达索引，则返回 false。如果到达数组末尾，则返回 true。
最大可达索引是你遇到的元素的可达索引的最大值。元素的可达索引是其索引加上其值。
| 索引 | 0 | 1 | 2 | 3 | 4 |
| 好吗？ | 是（1≤2） | 是（2≤4） | 是（3≤4） | 是（4≤4） | |
| 价值 | 2 | 3 | 1 | 1 | 4 |
| 可达索引 | 2 | 4 | 3 | 4 | 8 |
| 最大可达索引 | 2 | 4 | 4 | 4 | 8 |
| 索引 | 0 | 1 | 2 | 3 | 4 |
| 好吗？ | 是（1≤3） | 是（2≤3） | 是（3≤3） | 没有（4>3） | |
| 价值 | 3 | 2 | 1 | 0 | 4 |
| 可达索引 | 3 | 3 | 3 | 3 | |
| 最大可达索引 | 3 | 3 | 3 | 3 |