@@ -0,0 +1,2251 @@
+package JumpGameII;%0A%0A/**%0A * User: Danyang%0A * Date: 1/17/2015%0A * Time: 23:50%0A *%0A * Given an array of non-negative integers, you are initially positioned at the first index of the array.%0A%0A     Each element in the array represents your maximum jump length at that position.%0A%0A     Your goal is to reach the last index in the minimum number of jumps.%0A%0A     For example:%0A     Given array A = %5B2,3,1,1,4%5D%0A%0A     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.)%0A */%0Apublic class Solution %7B%0A    /**%0A     * f%5Bi%5D denotes the max reachable%0A     * f%5Bi%5D = max(f%5Bi-1%5D, A%5Bi%5D+i) if reachable from f%5Bi-1%5D%0A     * d%5Bi%5D denotes the min number of steps%0A     * d%5Bi%5D = min(d%5Bi-k%5D+1, d%5Bi%5D) if reachable %5Bforward%5D%0A     * --%3E d%5Bi+k%5D = min(d%5Bi%5D+1, d%5Bi+k%5D)%0A     *%0A     * O(n%5E2)%0A     * @param A%0A     * @return%0A     */%0A    public int jump_TLE(int%5B%5D A) %7B%0A        if(A.length==1)%0A            return A%5B0%5D%3E=0? 0: -1;%0A%0A        int %5B%5D f = new int%5BA.length%5D;%0A        int %5B%5D d = new int%5BA.length%5D;%0A        f%5B0%5D = A%5B0%5D;%0A        d%5B0%5D = 0;%0A        for(int i=1; i%3CA.length; i++) %7B%0A            if(i%3C=f%5B0%5D)%0A                d%5Bi%5D = 1;%0A            else%0A                d%5Bi%5D = Integer.MAX_VALUE;%0A        %7D%0A%0A        for(int i=1; i%3CA.length; i++) %7B%0A            if(f%5Bi-1%5D%3Ci)%0A                return -1;%0A            f%5Bi%5D = Math.max(f%5Bi-1%5D, A%5Bi%5D+i);%0A            for(int j=i+1; j%3CMath.min(A.length, f%5Bi%5D+1); j++)%0A                d%5Bj%5D = Math.min(d%5Bj%5D, d%5Bi%5D+1);%0A        %7D%0A        return d%5BA.length-1%5D;%0A    %7D%0A%0A    /**%0A     * Two Pointers - Sliding Window%0A     * Flattened bfs%0A     *%0A     * O(n) every node is visited no more than once.%0A     * @param A%0A     * @return%0A     */%0A    public int jump(int%5B%5D A) %7B%0A        if(A.length==1)%0A            return A%5B0%5D%3E=0? 0: -1;%0A        int f = A%5B0%5D;%0A        int l = 1;%0A        int r = f;%0A        int cnt = 1;%0A        while(f%3CA.length-1) %7B%0A            for(int i=l; i%3C=r; i++)%0A                f = Math.max(f, A%5Bi%5D+i);%0A            if(f%3C=r)%0A                return -1;%0A            l = r+1;%0A            r = f;%0A            cnt++;%0A        %7D%0A        return cnt;%0A    %7D%0A%0A    public static void main(String%5B%5D args) %7B%0A        int ret = new Solution().jump(new int%5B%5D%7B2, 3, 1, 1, 4%7D);%0A        assert ret==2;%0A    %7D%0A%7D

dp vs. flattened bfs