55 Jump Game
Python3
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 |
# Author: Huahua # Time complexity: O(n^2) # Space complexity: O(n) class Solution: def canJump(self, nums: List[int]) -> bool: n = len(nums) @cache def dp(i: int) -> bool: """Returns whether we can reach n - 1 from i.""" if i >= n - 1: return True if i + nums[i] >= n - 1: return True for s in range(1, nums[i] + 1): if dp(i + s): return True return False return dp(0) |
45 Jump Game II
Python3
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 |
# Author: Huahua # Time complexity: O(n^2) # Space complexity: O(n) class Solution: def jump(self, nums: List[int]) -> int: n = len(nums) @cache def dp(i: int) -> int: """Min steps to reach n - 1 from i.""" if i >= n - 1: return 0 if i + nums[i] >= n - 1: return 1 ans = n for s in range(1, nums[i] + 1): ans = min(ans, dp(i + s) + 1) return ans return dp(0) |
请尊重作者的劳动成果,转载请注明出处!花花保留对文章/视频的所有权利。
如果您喜欢这篇文章/视频,欢迎您捐赠花花。
If you like my articles / videos, donations are welcome.
Be First to Comment