Python DP


  • 0
    B
    class Solution(object):
        def canCross(self, stones):
            """
            :type stones: List[int]
            :rtype: bool
            """
            if (len(stones) <= 1):
                return True
            if (stones[1] != 1):
                return False
            hash = {}
            for idx, v in enumerate(stones):
                hash[v] = idx
    
            dp = [set() for _ in range(len(stones))]
            dp[1].add(1)
    
            for i in range(1, len(stones)):
                for val in dp[i]:
                    if (stones[i] + val + 1) in hash:
                        dp[hash[stones[i] + val + 1]].add(val + 1)
                    if (stones[i] + val - 1) in hash:
                        if (val - 1) > 0:
                            dp[hash[stones[i] + val - 1]].add(val - 1)
                    if (stones[i] + val) in hash:
                        dp[hash[stones[i] + val]].add(val)
    
            return (not len(dp[-1]) == 0)

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.