leetcode-dp

55. Jump Game.py

class Solution:
     """
    Thought Process:
        DP: Since if we can reach the current position relies one previous position.
        
        Let's define our subproblem. dp[i]: if we can reach position i
        
        base case i= 0:
            dp[0] = True
        
        [2,3,1,1,4]
           i
         j
             i
         j j
               i
                 i
        current subproblems relies on all smaller subproblems dp[j]
             dp[i] = True if dp[j] and nums[j]+j >= i
        our goal is to return dp[n-1]
        
        Greedy:
            at each step, we always choose maximum position that I can reach.
            
            if max_pos < i: return False
            
            how to calculate max_pos = max(max_pos, nums[i]+i)
    """
    def canJump(self, nums: List[int]) -> bool:
        """
        dp[i]: whetehr we can jump at this position i from the starting point(i=0), 0<=i<=n-1
        
        T: O(n**2)
        S: O(n)
        
        It won't get accepted because time limited problem for python3 but it worked for java.
        """
        n = len(nums)
        if n == 1:
            return True
        dp = [False for _ in range(n)]
        dp[0] = True
        
        for i in range(1, n):
            for j in range(i):
                if j + nums[j] >= i and dp[j]:
                    dp[i] = True
                    break
        return dp[-1]
    
    def canJump(self, nums: List[int]) -> bool:
        """
        For DP, we think in another way. The current state only relies on the last state instead of all the state, then we can have linear run time.
        
        dp[i]: represents maximum capacity we can jump at positin i.
        
        T: O(n)
        S: O(n)
        """
        n = len(nums)
        if n == 1:
            return True
        dp = [0 for _ in range(n)]
        
        for i in range(1, n):
            # we can either stop at position at i-1 or not stop at position i-1
            dp[i] = max(dp[i-1], nums[i-1]) - 1
            # Step3: Think about how to return our target from our memorization table.
            if dp[i] < 0:
                return False
        return True