Jump Game II · 數據結構與算法/leetcode/lintcode題解

# Jump Game II ### Source - lintcode: [(117) Jump Game II](http://www.lintcode.com/en/problem/jump-game-ii/) ~~~ 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. Your goal is to reach the last index in the minimum number of jumps. Example Given array A = [2,3,1,1,4] The minimum number of jumps to reach the last index is 2. (Jump 1 step from index 0 to 1, then 3 steps to the last index.) ~~~ ### 題解(自頂向下-動態規劃) 首先來看看使用動態規劃的解法，由于復雜度較高在A元素較多時會出現[TLE](# "Time Limit Exceeded 的簡稱。你的程序在 OJ 上的運行時間太長了，超過了對應題目的時間限制。")，因為時間復雜度接近 O(n3)O(n^3)O(n3). 工作面試中給出動規的實現就挺好了。 1. State: f[i] 從起點跳到這個位置最少需要多少步 1. Function: f[i] = MIN(f[j]+1, j < i && j + A[j] >= i) 取出所有能從j到i中的最小值 1. Initialization: f[0] = 0，即一個元素時不需移位即可到達 1. Answer: f[n-1] ### C++ Dynamic Programming ~~~ 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]; } }; ~~~ ### 源碼分析狀態轉移方程為 ~~~ if ((steps[j] != INT_MAX) && (j + A[j] >= i)) { steps[i] = steps[j] + 1; break; } ~~~ 其中break即體現了MIN操作，最開始滿足條件的j即為最小步數。 ### 題解(貪心法-自底向上) 使用動態規劃解Jump Game的題復雜度均較高，這里可以使用貪心法達到線性級別的復雜度。貪心法可以使用自底向上或者自頂向下，首先看看我最初使用自底向上做的。對A數組遍歷，找到最小的下標`min_index`，并在下一輪中用此`min_index`替代上一次的`end`, 直至`min_index`為0，返回最小跳數`jumps`。以下的實現有個 bug，細心的你能發現嗎？ ### C++ greedy from bottom to top, bug version ~~~ 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; int jumps = 0; int last_index = N; int min_index = N; for (int i = N - 1; i >= 0; --i) { if (i + A[i] >= last_index) { min_index = i; } if (0 == min_index) { return ++jumps; } if ((0 == i) && (min_index < last_index)) { ++jumps; last_index = min_index; i = last_index - 1; } } return jumps; } }; ~~~ ### 源碼分析使用jumps記錄最小跳數，last_index記錄離終點最遠的坐標，min_index記錄此次遍歷過程中找到的最小下標。以上的bug在于當min_index為1時，i = 0, for循環中仍有--i，因此退出循環，無法進入`if (0 == min_index)`語句，因此返回的結果會小1個。 ### C++ greedy, from bottom to top ~~~ class Solution { public: /** * @param A: A list of lists of integers * @return: An integer */ int jump(vector<int> A) { if (A.empty()) { return 0; } const int N = A.size() - 1; int jumps = 0, end = N, min_index = N; while (end > 0) { for (int i = end - 1; i >= 0; --i) { if (i + A[i] >= end) { min_index = i; } } if (min_index < end) { ++jumps; end = min_index; } else { // cannot jump to the end return -1; } } return jumps; } }; ~~~ ### 源碼分析之前的 bug version 代碼實在是太丑陋了，改寫了個相對優雅的實現，加入了是否能到達終點的判斷。在更新`min_index`的內循環中也可改為如下效率更高的方式： ~~~ for (int i = 0; i != end; ++i) { if (i + A[i] >= end) { min_index = i; break; } } ~~~ ### 題解(貪心法-自頂向下) 看過了自底向上的貪心法，我們再來瞅瞅自頂向下的實現。自頂向下使用`farthest`記錄當前坐標出發能到達的最遠坐標，遍歷當前`start`與`end`之間的坐標，若`i+A[i] > farthest`時更新`farthest`(尋找最小跳數)，當前循環遍歷結束時遞推`end = farthest`。`end >= A.size() - 1`時退出循環，返回最小跳數。 ### C++ ~~~ /** * http://www.jiuzhang.com/solutions/jump-game-ii/ */ class Solution { public: /** * @param A: A list of lists of integers * @return: An integer */ int jump(vector<int> A) { if (A.empty()) { return 0; } const int N = A.size() - 1; int start = 0, end = 0, jumps = 0; while (end < N) { int farthest = end; for (int i = start; i <= end; ++i) { if (i + A[i] >= farthest) { farthest = i + A[i]; } } if (end < farthest) { ++jumps; start = end + 1; end = farthest; } else { // cannot jump to the end return -1; } } return jumps; } }; ~~~