2020-05-20

LeetCode 55. Jump Game

Problem

1. 题目简述

给出一个整形非负数组，初始在index为0的位置，每个位置上的数代表其所能跳跃的最大长度（不是只能跳跃该长度），问是否能够跳到达数组末尾位置。例如：

Example 1:

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:

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.

2. 算法思路

Brute Force

首先，我们能想到的最傻的办法就是暴力求解。设函数F(x)为从x节点能否到达尾结点，我们假设从0开始，0节点的最大jump值为5，然后我们将步长step从1到5进行遍历，如果能够达到末尾节点，则为0，伪代码如下：

F(x) :
    if x >= n - 1
        return true;
    step = nums[x]
    for i from 1 to step:
        if F(x + i):
            return true;
        else:
            continue;
    return false;

最坏情况，时间复杂度为O(2^n)，空间复杂度O(n)。

对于暴力破解法显然是不优雅的，每次只遍历一步，而且存在大量的重复计算，比如对于这种情况：

Index	0	1	2	3	4	5	6
nums	5	4	3	2	1	0	0
从index为0开始时，首次步长为1，跳转到index为1，再到index为2，以此类推，最终返回的时候我们知道步长为1时，无法到达末尾位置；然后我们调整步长为2，此时，我们直接到index为2的节点，判断位置为2的节点能否到达末尾，但是实际上，在我们计算步长为1的时候，index为2位置能否到达末尾节点我们已经知晓了，是false的，其实没必要计算，这个就是我们需要DP来优化的子问题。

Dynamic Programming

DP1 top-down：

记录一个memo数组，长度为n，表示index处能否到达末尾位置，memo[n-1]为1，其余初始为0。然后开始递归调用，top-down的算法都是要递归的。

DP2 bottom-up:
记录一个memo数组，bottom-up算法就是要从base case开始进行计算，一直到目标target，本题中，base case是memo[n-1]=1，所以我们要从n-2开始往回遍历，判断n-2节点能否到达n-1节点，如果能，则memo[n-2]=1，不能则为0，一直遍历到memo[0]，返回memo[0]。

两种DP算法时间复杂度均为O(n^2)，空间复杂度为O(n)。

Greedy

本题的最优解为贪心法，那么什么情况下应该使用贪心法呢？其实贪心法算是动态规划的一种特殊形式，贪心法是要找出当前的最优解，而当前的最优解却不一定是全局最优解，这个在后面的题目中再慢慢体会。

所以我们记录一个farthest表示从0到当前节点，所能到达的最大index。
$$farthest=max(i+nums[i],farthest) (0<=i<n-1)$$

这里我们需要注意一种情况，正如之前的例子，如果不能到达末尾节点，中间一定有某个为0的节点，且该节点的所有前置节点最远只能到达该节点。所以每次遍历时，需要判断farthest和i的关系，如果 farthest<=i 则代表i节点为0且无法到达后面的节点了。

3. 解法

暴力解法（直接抄leetcode上的solution了）


public class Solution {
    public boolean canJumpFromPosition(int position, int[] nums) {
        if (position == nums.length - 1) {
            return true;
        }

        int furthestJump = Math.min(position + nums[position], nums.length - 1);
        for (int nextPosition = position + 1; nextPosition <= furthestJump; nextPosition++) {
            if (canJumpFromPosition(nextPosition, nums)) {
                return true;
            }
        }

        return false;
    }

    public boolean canJump(int[] nums) {
        return canJumpFromPosition(0, nums);
    }
}

DP top-down

enum Index {
    GOOD, BAD, UNKNOWN
}

public class Solution {
    Index[] memo;

    public boolean canJumpFromPosition(int position, int[] nums) {
        if (memo[position] != Index.UNKNOWN) {
            return memo[position] == Index.GOOD ? true : false;
        }

        int furthestJump = Math.min(position + nums[position], nums.length - 1);
        for (int nextPosition = position + 1; nextPosition <= furthestJump; nextPosition++) {
            if (canJumpFromPosition(nextPosition, nums)) {
                memo[position] = Index.GOOD;
                return true;
            }
        }

        memo[position] = Index.BAD;
        return false;
    }

    public boolean canJump(int[] nums) {
        memo = new Index[nums.length];
        for (int i = 0; i < memo.length; i++) {
            memo[i] = Index.UNKNOWN;
        }
        memo[memo.length - 1] = Index.GOOD;
        return canJumpFromPosition(0, nums);
    }
}

DP bottom-up

enum Index {
    GOOD, BAD, UNKNOWN
}

public class Solution {
    public boolean canJump(int[] nums) {
        Index[] memo = new Index[nums.length];
        for (int i = 0; i < memo.length; i++) {
            memo[i] = Index.UNKNOWN;
        }
        memo[memo.length - 1] = Index.GOOD;

        for (int i = nums.length - 2; i >= 0; i--) {
            int furthestJump = Math.min(i + nums[i], nums.length - 1);
            for (int j = i + 1; j <= furthestJump; j++) {
                if (memo[j] == Index.GOOD) {
                    memo[i] = Index.GOOD;
                    break;
                }
            }
        }

        return memo[0] == Index.GOOD;
    }
}

Greedy


class Solution {

    public boolean canJump(int[] nums) {
        int farthest = 0;
        for (int i = 0; i < nums.length - 1; i++) {
            farthest = Math.max(farthest, i + nums[i]);
            if (farthest >= nums.length-1) {
                return true;
            }
            if (farthest <= i) {
                return false;
            }
        }
        return farthest >= nums.length-1;
    }
}

Maye's Life

Engineering · Thinking · Life