• API
• FAQ
• Tools
• Archive
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.
Not a member of Pastebin yet?