Share a Python DP/Dic solution


  • 0
    P
    class Solution(object):
        def canCross(self, stones):
            """
            :type stones: List[int]
            :rtype: bool
            """
            # last step to reach position s
            dp = {}
            for i, s in enumerate(stones):
                if i == 0:
                    dp[1] = set([i])
                # s can be reached
                elif i != len(stones) - 1 and s in dp:
                    for u in dp[s]:
                        jump = s - stones[u]
                        for k in range(s + jump - 1, s + jump + 2):
                            # cannot jump to current position
                            if k > s:
                                if k not in dp:
                                    dp[k] = set()
                                dp[k].add(i)
            return stones[-1] in dp
    

Log in to reply
 

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