夯实算法-跳跃游戏

题目：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)