Jump Game II -- LeetCode

 
這道題是Jump Game的擴展，區別是這道題不僅要看能不能到達終點，而且要求到達終點的最少步數。其實思路和Jump Game還是類似的，只是原來的全局最優現在要分成step步最優和step-1步最優（假設當前步數是step）。當走到超過step-1步最遠的位置時，說明step-1不能到達當前一步，我們就可以更新步數，將step+1。時間復雜度仍然是O(n)，空間復雜度也是O(1)。代碼如下：

public int jump(int[] A) {
    if(A==null || A.length==0)
        return 0;
    int lastReach = 0;
    int reach = 0;
    int step = 0;
    for(int i=0;i<=reach&&ilastReach)
        {
            step++;
            lastReach = reach;
        }
        reach = Math.max(reach,A[i]+i);
    }
    if(reach動態規劃是面試中特別是onsite中非常重要的類型，一般面試中模型不會過於復雜，所以大家可以熟悉一下比較經典的幾個題，比如Jump
 Game，Maximum
 Subarray等。