@@ -0,0 +1,1016 @@
+// Naive recursive solution.%0A// Depending on array values, branching can be huge, so runtime is O(2%5En) and O(n) space, because%0A// in the worst case recursion tree height equals to number of elements in the array: %5B1,1,1,...%5D.%0Aclass Solution %7B%0A  public boolean canJump(int%5B%5D nums) %7B%0A    return jump(nums, 0);%0A  %7D%0A%0A  private boolean jump(int%5B%5D nums, int i) %7B%0A    if (i %3E= nums.length) return false;%0A    if (i == nums.length - 1) return true;%0A    for (int j = 1; j %3C= nums%5Bi%5D; j++) %7B%0A      if (jump(nums, i + j)) return true;%0A    %7D%0A    return false;%0A  %7D%0A%7D%0A%0A// Dynamic programming solution (passes).%0A// Runs in O(n%5E2) time and O(1) space.%0A// Idea is determining if you can reach current position (index + step %3E= current) from any%0A// other position (index).%0Aclass Solution %7B%0A  public boolean canJump(int%5B%5D nums) %7B%0A    for (int i = 1; i %3C nums.length; i++) %7B%0A      int j = i - 1;%0A      while (j %3E= 0) %7B%0A        if (j + nums%5Bj%5D %3E= i) break;%0A        --j;%0A      %7D%0A      if (j %3C 0) return false;%0A    %7D%0A    return true;%0A  %7D%0A%7D%0A

add solution