✌粤嵌—2024/3/11—跳跃游戏

代码实现：

方法一：递归+记忆化

int path;
int used[10000];bool dfs(int *nums, int numsSize) {if (path == numsSize - 1) {return true;}for (int i = 1; i <= nums[path]; i++) {if (used[path + i]) {continue;}path += i;used[path] = 1;if (dfs(nums, numsSize)) {return true;}path -= i;}return false;
}bool canJump(int *nums, int numsSize) {path = 0;memset(used, 0, sizeof(int) * numsSize);return dfs(nums, numsSize);
}

方法二：动态规划

bool canJump(int *nums, int numsSize) {bool dp[numsSize]; // 能否到达dp[i]memset(dp, false, sizeof(dp));dp[0] = true;for (int i = 1; i < numsSize; i++) {for (int j = 0; j < i; j++) {if (dp[j] && nums[j] + j >= i) {dp[i] = true;break;}}}return dp[numsSize - 1];
}

方法三：贪心

每次取最大跳跃步数（取最大覆盖范围）

bool canJump(int *nums, int numsSize) {if (numsSize == 1) {return true;}int cover = 0;for (int i = 0; i <= cover; i++) {cover = cover > i + nums[i] ? cover : i + nums[i];if (cover >= numsSize - 1) {return true;}}return false;
}