Open cs-cordero opened 5 years ago
Based on what Leetcode says about my runtime and memory usage, there's probably a better way to do this.
Runtime: 76 ms, faster than 32.60% of Python3 online submissions for Jump Game II. Memory Usage: 15.2 MB, less than 5.00% of Python3 online submissions for Jump Game II.
class Solution: def jump(self, nums: List[int]) -> int: dp = [len(nums) for _ in range(len(nums))] dp[0] = 0
for jumpman in range(len(dp)):
current_jump_count = dp[jumpman]
possible_jump_count = nums[jumpman]
end_jump = min(len(dp)-1, jumpman+possible_jump_count)
for next_jump in range(end_jump, jumpman, -1):
if dp[next_jump] <= current_jump_count+1:
break
dp[next_jump] = current_jump_count + 1
return dp[-1]
🎵 Jumpman. Jumpman. Jumpman. Them boys up to something 🎵
Link: https://leetcode.com/problems/jump-game-ii/