'''
TC of recursive -> exponential
SC of recursive -> O(n)
TC of dp -> O(n^2)
SC of dp -> O(n)
'''
import numpy
def find_min_jumps_recur(nums, idx):
  # TCs
  if idx == 0:
    return 0

  min_jumps = 9999
  for start_index in range(0, idx):
    if idx <= nums[start_index]+start_index:
      min_jumps = min(min_jumps, find_min_jumps_recur(nums, start_index)+1)

  return min_jumps

def find_min_jumps_dp(nums):
  dp = numpy.full((len(nums)), 9999)
  dp[0] = 0
  for idx in range(1, len(dp)):
    dp[idx] = 9999
    for start_index in range(0, idx):
      if idx <= nums[start_index]+start_index:
        dp[idx] = min(dp[idx], dp[start_index]+1)

  print dp


def main():
  nums = [2,0,1,1,4]
  print find_min_jumps_recur(nums, len(nums)-1)
  find_min_jumps_dp(nums)

if __name__ == "__main__":
  main()