• Jump Game
  • In Categories Of
  • Algorithm
  • Tagged With
  • Greedy
  • Dynamic Programming
  • Questions

    这两题明眼看是序列形动态规划的题,但是时间复杂度上其实并不好,会出现超时的情况。而用贪心法则能避免。单独拿出来记录一下贪心法。尤其是Jump Game II 的做法非常巧妙。

    Jump Game

    动态规划解法,无法被AC, c++的解法会超时。

    class Solution {
    public:
        /**
         * @param A: A list of integers
         * @return: The boolean answer
         */
        bool canJump(vector<int> A) {
            if (A.empty()) {
                return true;
            }
    
            vector<bool> jumpto(A.size(), false);
            jumpto[0] = true;
    
            for (int i = 1; i != A.size(); ++i) {
                for (int j = i - 1; j >= 0; --j) {
                    if (jumpto[j] && (j + A[j] >= i)) {
                        jumpto[i] = true;
                        break;
                    }
                }
            }
    
            return jumpto[A.size() - 1];
        }
    };
    

    贪心法的解法,很快。

    维护一个最远能到达的变量,如果当前位置的值超过了这个变量那么更新该变量。从头循环到尾,如果现在的位置超过了最远能到达的位置,那说明到不了最后,返回false。

    class Solution {
    public:
        /**
         * @param A: A list of integers
         * @return: The boolean answer
         */
        bool canJump(vector<int> A) {
            // write you code here
    
            int reachable = 0;
            for (int i = 0; i < A.size(); ++i){
                if (i > reachable){
                    return false;
                }
                reachable = max(reachable, i + A[i]);
            }
            return true;
        }
    };
    

    Jump Game II

    动态规划的和之前的没什么大差别,把维护的数组类型从bool换成了int记录步数。

    class Solution {
    public:
        /**
         * @param A: A list of lists of integers
         * @return: An integer
         */
        int jump(vector<int> A) {
            if (A.empty()) {
                return -1;
            }
    
            const int N = A.size() - 1;
            vector<int> steps(N, INT_MAX);
            steps[0] = 0;
    
            for (int i = 1; i != N + 1; ++i) {
                for (int j = 0; j != i; ++j) {
                    if ((steps[j] != INT_MAX) && (j + A[j] >= i)) {
                        steps[i] = steps[j] + 1;
                        break;
                    }
                }
            }
    
            return steps[N];
        }
    };
    

    贪心法:

    // Time:  O(n)
    // Space: O(1)
    
    class Solution {
    public:
        /**
         * @param A: A list of lists of integers
         * @return: An integer
         */
        int jump(vector<int> A) {
            int jump_count = 0;
            int reachable = 0;
            int curr_reachable = 0;
            for (int i = 0; i < A.size(); ++i) {
                if (i > curr_reachable) {
                    // current jumps are not enough,
                    // jump one more step, which enlarges curr_reachable to reachable.
                    curr_reachable = reachable;
                    ++jump_count;
                }
                reachable = max(reachable, i + A[i]);
            }   
    
            return jump_count;
        }
    };
    
    

    reference