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