55. Jump Game

"""
main idea: Greedy - start from last postion, record the first position that can
jump to last position, then update last position to current idex.  Check if last position can go back to idx = 0.  
start from last position, moving towards back. each time check at current position if one can jump to the last position, update the last position. Condition to determine jump will success: can last position move back to start of array.
"""
class Solution:
    def canJump(self, nums: List[int]) -> bool:
        # time O(N) space O(1)
        last_pos = len(nums)-1
        for i in range(len(nums)-1,-1,-1):
            if i + nums[i] >= last_pos:
                last_pos = i
        return last_pos == 0
# within valid range of right most position,  
#track the right most range current position can go
# when ever the right most reaches last position, means we can reach to the end.
# if by the time the loop ends, we can not reach the last point, return False 
class Solution:
    def canJump(self, A: List[int]) -> bool:
        n = len(A)
        right_most = 0
        for i in range(n):
            if i <= right_most:
                right_most = max(right_most, i+A[i])
                if right_most >= n-1:
                    return True 
        return False 

# time O(N^2) space O(N)
class Solution:
    def canJump(self, nums: List[int]) -> bool:
        n = len(nums)
        dp = [False] * n
        dp[0] = True 
        for i in range(1,n):
            for j in range(i):
                if dp[j] == True and j + nums[j] >= i:
                    dp[i] = True 
                    break
        return dp[n-1]

class Solution:
    def canJump(self, nums: List[int]) -> bool:
        # TLE time O(N) space O(N)  
        return self.btr(0,nums)
    
    def btr(self,start,arr):
        if start == len(arr) -1:
            return True
        farest = min(start+arr[start],len(arr)-1)
        for i in range(start+1,farest+1):
            if self.btr(i,arr): return True
        return False
######### slitly optimize :instead of from start to end, from end to start   (!! here only works with end to start )
class Solution:
    def canJump(self, nums: List[int]) -> bool:
        # TLE time O(N*N) space O(N)  
        return self.btr(0,nums)
    
    def btr(self,start,arr):
        if start == len(arr) -1:
            return True
        farest = min(start+arr[start],len(arr)-1)
        for i in range(farest,start,-1):
            if self.btr(i,arr): return True
        return False

class Solution:
    def canJump(self, nums: List[int]) -> bool:
        # TLE time O(N*N) space O(N)
        self.memo = [0]* len(nums)
        self.memo[-1] = 1
        return self.dp(0,nums)
    
    
    def dp(self,start,arr):
        if self.memo[start] != 0:
            return self.memo[start] == 1
        farest = min(start+arr[start],len(arr)-1)
        for i in range(start+1,farest+1):
            if self.dp(i,arr): 
                self.memo[start] = 1
                return True
        self.memo[start] = -1
        return False

class Solution:
    def canJump(self, nums: List[int]) -> bool:
        # TLE time O(N*N) space O(N)
        memo = [0]* len(nums)
        memo[-1] = 1
        for i in range(len(nums)-2,-1,-1):
            farest = min(nums[i]+i,len(nums)-1)
            for j in range(i+1,farest+1):
                if memo[j] == 1:
                    memo[i] = 1
                    break
        return memo[0] == 1