Jump Game
题目链接：
https://leetcode.cn/problems/jump-game/?favorite=2cktkvj

You are given an integer array nums. You are initially positioned at the array’s first index, and each element in the array represents your maximum jump length at that position.

Return true if you can reach the last index, or false otherwise.

Example 1:

1
2
3
Input: nums = [2,3,1,1,4]
Output: true
Explanation: Jump 1 step from index 0 to 1, then 3 steps to the last index.

Example 2:

1
2
3
Input: nums = [3,2,1,0,4]
Output: false
Explanation: You will always arrive at index 3 no matter what. Its maximum jump length is 0, which makes it impossible to reach the last index.

Constraints:

1 <= nums.length <= 104
0 <= nums[i] <= 105

解题思路：

定义一个数组 dp，其中 dp[i] 表示能否从数组的第一个位置到达第 i 个位置。

对于每个位置 i，我们可以从前面的位置 j 到达当前位置，如果存在一个位置 j，满足 dp[j] 为 true，并且从位置 j 能够到达位置 i，则 dp[i] 也为 true。

最终的答案就是 dp 数组的最后一个元素的值。

源代码： 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
 func canJump(_ nums: [Int]) -> Bool {
    var dp = [Bool](repeating: false, count: nums.count)
    dp[0] = true

    for i in 1..<nums.count {
        for j in (0..<i).reversed() {
            if dp[j] && j + nums[j] >= i {
                dp[i] = true
                break
            }
        }
    }

    return dp[nums.count - 1]
}

该算法的时间复杂度为 O(n^2)，其中 n 是数组 nums 的长度。空间复杂度为 O(n)，因为我们需要使用一个数组来保存 dp 数组的值。虽然这个算法的时间复杂度较高，但是对于较小的数组，仍然可以得到正确的答案。