Guest User

Untitled

a guest
May 23rd, 2019
60
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. '''
  2. TC of recursive -> exponential
  3. SC of recursive -> O(n)
  4. TC of dp -> O(n^2)
  5. SC of dp -> O(n)
  6. '''
  7. import numpy
  8. def find_min_jumps_recur(nums, idx):
  9. # TCs
  10. if idx == 0:
  11. return 0
  12.  
  13. min_jumps = 9999
  14. for start_index in range(0, idx):
  15. if idx <= nums[start_index]+start_index:
  16. min_jumps = min(min_jumps, find_min_jumps_recur(nums, start_index)+1)
  17.  
  18. return min_jumps
  19.  
  20. def find_min_jumps_dp(nums):
  21. dp = numpy.full((len(nums)), 9999)
  22. dp[0] = 0
  23. for idx in range(1, len(dp)):
  24. dp[idx] = 9999
  25. for start_index in range(0, idx):
  26. if idx <= nums[start_index]+start_index:
  27. dp[idx] = min(dp[idx], dp[start_index]+1)
  28.  
  29. print dp
  30.  
  31.  
  32. def main():
  33. nums = [2,0,1,1,4]
  34. print find_min_jumps_recur(nums, len(nums)-1)
  35. find_min_jumps_dp(nums)
  36.  
  37. if __name__ == "__main__":
  38. main()
RAW Paste Data