# Jump Game ### Source - lintcode: [(116) Jump Game](http://www.lintcode.com/en/problem/jump-game/) ~~~ Given an array of non-negative integers, you are initially positioned at the first index of the array. Each element in the array represents your maximum jump length at that position. Determine if you are able to reach the last index. Example A = [2,3,1,1,4], return true. A = [3,2,1,0,4], return false. ~~~ ### 題解(自頂向下-動態規劃) 1. State: f[i] 從起點出發能否達到i 1. Function: `f[i] = OR (f[j], j < i ~\&\&~ j + A[j] \geq i)`, 狀態 jjj 轉移到 iii, 所有小于i的下標j的元素中是否存在能從j跳轉到i得 1. Initialization: f[0] = true; 1. Answer: 遞推到第 N - 1 個元素時，f[N-1] 這種自頂向下的方法需要使用額外的 O(n)O(n)O(n) 空間，保存小于N-1時的狀態。且時間復雜度在惡劣情況下有可能變為 1+2+?+n=O(n2)1 + 2 + \cdots + n = O(n^2)1+2+?+n=O(n2), 出現 [TLE](# "Time Limit Exceeded 的簡稱。你的程序在 OJ 上的運行時間太長了，超過了對應題目的時間限制。") 無法AC的情況，不過工作面試能給出這種動規的實現就挺好的了。 ### C++ from top to bottom ~~~ 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]; } }; ~~~ ### 題解(自底向上-貪心法) 題意為問是否能從起始位置到達最終位置，我們首先分析到達最終位置的條件，從坐標i出發所能到達最遠的位置為 f[i]=i+A[i]f[i] = i + A[i]f[i]=i+A[i]，如果要到達最終位置，即存在某個 iii 使得f[i]≥N?1f[i] \geq N - 1f[i]≥N?1, 而想到達 iii, 則又需存在某個 jjj 使得 f[j]≥i?1f[j] \geq i - 1f[j]≥i?1. 依此類推直到下標為0. **以下分析形式雖為動態規劃，實則貪心法！** 1. State: f[i] 從 iii 出發能否到達最終位置 1. Function: f[j]=j+A[j]≥if[j] = j + A[j] \geq if[j]=j+A[j]≥i, 狀態 jjj 轉移到 iii, 置為`true` 1. Initialization: 第一個為`true`的元素為 `A.size() - 1` 1. Answer: 遞推到第 0 個元素時，若其值為`true`返回`true` ### C++ greedy, from bottom to top ~~~ class Solution { public: /** * @param A: A list of integers * @return: The boolean answer */ bool canJump(vector<int> A) { if (A.empty()) { return true; } int index_true = A.size() - 1; for (int i = A.size() - 1; i >= 0; --i) { if (i + A[i] >= index_true) { index_true = i; } } return 0 == index_true ? true : false; } }; ~~~ ### 題解(自頂向下-貪心法) 針對上述自頂向下可能出現時間復雜度過高的情況，下面使用貪心思想對i進行遞推，每次遍歷A中的一個元素時更新最遠可能到達的元素，最后判斷最遠可能到達的元素是否大于 `A.size() - 1` ### C++ greedy, from top to bottom ~~~ class Solution { public: /** * @param A: A list of integers * @return: The boolean answer */ bool canJump(vector<int> A) { if (A.empty()) { return true; } int farthest = A[0]; for (int i = 1; i != A.size(); ++i) { if ((i <= farthest) && (i + A[i] > farthest)) { farthest = i + A[i]; } } return farthest >= A.size() - 1; } }; ~~~