2019-02-02 第六天(#55, #45)

#55 Jump Game

题目地址：https://leetcode.com/problems/jump-game/
标准的动态规划问题，其实最好先用蠢方法（递归）自己试一遍，推导出递推公式，然后转化为for循环。

动态规划 (时间复杂度O(n^2))

把数组内的每一个位置标记为”GOOD"或者"BAD"，前者代表可以从此处直接抵达终点，后者代表不可以。
Base case是确定的：数组中的最后一个位置必定是GOOD。那么目标就变成了从后面的位置往前推。
前面位置是否为GOOD的判断规则：如果从这个位置往后跳能到达任何GOOD位置，那么这个位置也是GOOD，否则为BAD。所谓“往后跳“，就是指这个位置能向右达到的最远距离。

递推公式

得到递推公式就很简单了，可以用DP做。代码如下：

class Solution {
public:
    bool canJump(vector<int>& nums) {
        if(nums.empty()) return true;
        // 0: Unknown, 1: Good, -1: Bad
        vector<int> canJumpFrom(nums.size(), 0);
        canJumpFrom.at(nums.size()-1) = 1;
        for(int ind = nums.size()-2; ind >= 0; --ind){
            int furtherestPoint = min(ind+nums.at(ind), (int)nums.size()-1);
            for(int pos = furtherestPoint; pos > ind; --pos){
                if(canJumpFrom.at(pos) == 1){
                    canJumpFrom.at(ind) = 1;
                    break;
                }
                canJumpFrom.at(ind) = -1;
            }
        }
        if(canJumpFrom.at(0) == 1)
            return true;
        else
            return false;
    }
};

这个方法打败了22.2%的人。考虑到能做出这个题至少都是用动态规划做的，我感觉我写的还可以。
时间复杂度为O(n^2)，空间复杂度为O(n)，用来存GOOD和BAD的数组占用了一定的空间。

贪婪算法（时间复杂度O(n)）

我对贪婪算法(Greedy Algorithm)知之甚少，这里只能说是依葫芦画瓢；总体思路依然是从后往前搜索，如果当前的位置为GOOD（能抵达终点），就把当前的位置作为新的终点。代码如下：

class Solution {
public:
    bool canJump(vector<int>& nums) {
        if(nums.empty()) return true;
        int boundary = nums.size()-1;
        for(int ind = nums.size()-1; ind >=0; ind--){
            if(ind + nums.at(ind) >= boundary)
                boundary = ind;
        }
        
        return boundary == 0;
    }
};

时间复杂度为O(n), 空间复杂度为O(1)。这种算法甚至不需要保存GOOD/BAD数组，我只要能达到起点即可。这么说倒是有点像“倒着走迷宫”的思路。

#45 Jump Game II

问题地址：https://leetcode.com/problems/jump-game-ii/
不愧是Hard，我基本快缴械投降了。难还是难在很难想出Dynamic Programming的递推公式来。

初见-Dynamic Programming(时间复杂度O(n^2))

思路倒是很简单，从起点开始不断增长数组的长度，抵达终点的方法有两种：一步到位，或者从走中间。而当把起点也当成是“中间”的时候，这两种方法其实也可以合并为一种。走“中间”的步数就是走到中间所需步数再+1。
递推公式如下：

递推公式

具体实现：

class Solution {
public:
    
    int jump(vector<int>& nums) {
        vector<int> jumpNums(nums.size(), INT_MAX);
        jumpNums.at(0) = 0;
        for(int index = 0; index < nums.size(); ++index){
            for(int secInd = 0; secInd < index; secInd++){
                if(secInd + nums.at(secInd) >= index)
                    jumpNums.at(index) = min(jumpNums.at(index), jumpNums.at(secInd) + 1);
            }
        }
        
        return *jumpNums.rbegin();
    }
};

时间复杂度O(n^2)，空间复杂度O(n)。