夯实算法-跳跃游戏

短命女 2024-03-31 15:33 53阅读 0赞

### ![0236183ef6be482cae666099c5c8a353.png][]题目：[LeetCode][] ###

给定一个非负整数数组 `nums` ，你最初位于数组的 **第一个下标** 。

数组中的每个元素代表你在该位置可以跳跃的最大长度。

判断你是否能够到达最后一个下标。

**示例 1：**

输入： nums = [2,3,1,1,4]
    输出： true
    解释： 可以先跳 1 步，从下标 0 到达下标 1, 然后再从下标 1 跳 3 步到达最后一个下标。
    复制代码

**示例 2：**

输入： nums = [3,2,1,0,4]
    输出： false
    解释： 无论怎样，总会到达下标为 3 的位置。但该下标的最大跳跃长度是 0 ， 所以永远不可能到达最后一个下标。
    复制代码

**提示：**

*  `1 <= nums.length <= 3`

### 解题思路 ###

记数组长度是nnn，从前往后跳，每一步，下标iii可以跳的最大长度是其元素\[i\]\[i\]\[i\]，意思就是每一步都有若干选择，可以跳 000，也可以跳\[i\]\[i\]\[i\]，问能否到达最后一个下标 n−1n-1n−1，很明显可以用动态规划解决。

状态转移方程是结果导向，换句话说就是要尽可能的以直接得到最终结果来定义状态。

记f(i)f(i)f(i)为能否跳跃到下标为 iii 的状态，那么 f(n−1)f(n-1)f(n−1) 就是整个问题的解。

如果从i−1i−1i−1位置跳，那么只要\[i−1\]\[i−1\]\[i−1\]大于等于111，并且f(i−1)f(i−1)f(i−1)也是TTT，就能达到位置iii；同理，如果从i−2i−2i−2位置跳，只要\[i−2\]\[i−2\]\[i−2\]大于等于222,并且f(i−2)f(i−2)f(i−2)是TTT即可，

可得到状态转移方程： f(i)=f(j)∧nums\[j\]≥i−j,j∈\[0,i−1\]f(i)=f(j)∧nums\[j\]≥i−j,j∈\[0,i−1\]f(i)=f(j)∧nums\[j\]≥i−j,j∈\[0,i−1\]

且明显f(0)=Tf(0)=Tf(0)=T。

### 代码实现 ###

public boolean canJump(int[] nums) {
        final int n = nums.length;
        boolean[] dp = new boolean[n];
        dp[0] = true;
        for (int i = 1; i < n; i++) {
            for (int j = 0; j < i; j++) {
                if (dp[j] && nums[j] >= i - j) {
                    dp[i] = true;
                }
            }
        }
        return dp[n - 1];
    }
    复制代码

### 复杂度分析 ###

*  空间复杂度：O(1)O(1)O(1)
 *  时间复杂度：O(n2)O(n^2)O(n2)

[0236183ef6be482cae666099c5c8a353.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/31/04fe442d7a6e4217872c7dd7730ddc5d.png
[LeetCode]: https://link.juejin.cn?target=https%3A%2F%2Fleetcode.cn%2Fproblems%2Fjump-game%2F