Jump Game

Question

  • lintcode:

(116) Jump Game

  1. Given an array of non-negative integers, you are initially positioned at the first index of the array.
  3. Each element in the array represents your maximum jump length at that position.
  5. Determine if you are able to reach the last index.
  7. Example
  8. A = [2,3,1,1,4], return true.
  10. A = [3,2,1,0,4], return false.

题解(自顶向下-动态规划)

  1. State: f[i] 从起点出发能否达到i
  2. Function: f[i] = OR (f[j], j < i ~\&\&~ j + A[j] \geq i), 状态 $$j$$ 转移到 $$i$$, 所有小于i的下标j的元素中是否存在能从j跳转到i得
  3. Initialization: f[0] = true;
  4. Answer: 递推到第 N - 1 个元素时，f[N-1]

这种自顶向下的方法需要使用额外的 O(n) 空间，保存小于N-1时的状态。且时间复杂度在恶劣情况下有可能变为 1 + 2 + \cdots + n = O(n^2), 出现 TLE 无法AC的情况，不过工作面试能给出这种动规的实现就挺好的了。

C++ from top to bottom

  1. class Solution {
  2. public:
  3.     /**
  4.      * @param A: A list of integers
  5.      * @return: The boolean answer
  6.      */
  7.     bool canJump(vector<int> A) {
  8.         if (A.empty()) {
  9.             return true;
  10.         }
  12.         vector<bool> jumpto(A.size(), false);
  13.         jumpto[0] = true;
  15.         for (int i = 1; i != A.size(); ++i) {
  16.             for (int j = i - 1; j >= 0; --j) {
  17.                 if (jumpto[j] && (j + A[j] >= i)) {
  18.                     jumpto[i] = true;
  19.                     break;
  20.                 }
  21.             }
  22.         }
  24.         return jumpto[A.size() - 1];
  25.     }
  26. };

题解(自底向上-贪心法)

题意为问是否能从起始位置到达最终位置，我们首先分析到达最终位置的条件，从坐标i出发所能到达最远的位置为 f[i] = i + A[i]，如果要到达最终位置，即存在某个 i 使得f[i] \geq N - 1, 而想到达 i, 则又需存在某个 j 使得 f[j] \geq i - 1. 依此类推直到下标为0.

以下分析形式虽为动态规划，实则贪心法！

  1. State: f[i] 从 $$i$$ 出发能否到达最终位置
  2. Function: $$f[j] = j + A[j] \geq i$$, 状态 $$j$$ 转移到 $$i$$, 置为true
  3. Initialization: 第一个为true的元素为 A.size() - 1
  4. Answer: 递推到第 0 个元素时，若其值为true返回true

C++ greedy, from bottom to top

  1. class Solution {
  2. public:
  3.     /**
  4.      * @param A: A list of integers
  5.      * @return: The boolean answer
  6.      */
  7.     bool canJump(vector<int> A) {
  8.         if (A.empty()) {
  9.             return true;
  10.         }
  12.         int index_true = A.size() - 1;
  13.         for (int i = A.size() - 1; i >= 0; --i) {
  14.             if (i + A[i] >= index_true) {
  15.                 index_true = i;
  16.             }
  17.         }
  19.         return 0 == index_true ? true : false;
  20.     }
  21. };

题解(自顶向下-贪心法)

针对上述自顶向下可能出现时间复杂度过高的情况，下面使用贪心思想对i进行递推，每次遍历A中的一个元素时更新最远可能到达的元素，最后判断最远可能到达的元素是否大于 A.size() - 1

C++ greedy, from top to bottom

  1. class Solution {
  2. public:
  3.     /**
  4.      * @param A: A list of integers
  5.      * @return: The boolean answer
  6.      */
  7.     bool canJump(vector<int> A) {
  8.         if (A.empty()) {
  9.             return true;
  10.         }
  12.         int farthest = A[0];
  14.         for (int i = 1; i != A.size(); ++i) {
  15.             if ((i <= farthest) && (i + A[i] > farthest)) {
  16.                 farthest = i + A[i];
  17.             }
  18.         }
  20.         return farthest >= A.size() - 1;
  21.     }
  22. };