python dfs


  • 0
    class Solution(object):
        def canCross(self, stones):
            """
            :type stones: List[int]
            :rtype: bool
            """
            
            cache={}
            if 0 not in stones or 1 not in stones:return False
            def dp(a,k):
                #print "(%d,%d)"%(a,k)
                if (a,k) in cache:return cache[(a,k)]
                if k==0:return False
                res=False
                if a not in stones:cache[(a,k)]=False;return False
                if a==stones[-1]:return True
                if k>1:res=(res or dp(a+k-1,k-1))
                res=(res or dp(a+k+1,k+1))
                res=(res or dp(a+k,k))
                cache[(a,k)]=res
                return res
            return dp(1,1)
    

Log in to reply
 

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