SHARE
TWEET

Untitled

a guest May 23rd, 2019 59 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
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
Not a member of Pastebin yet?
Sign Up, it unlocks many cool features!
 
Top