# Python - DP top-down with memoization

• ``````class Solution(object):
def canCross(self, stoneL):
"""
:type stones: List[int]
:rtype: bool
"""
stones = set(stoneL)    # change to set
def dp(i, k, mem):
if (i, k) in mem:
return mem[(i, k)]
if i == stoneL[-1]:
mem[(i, k)] = True
return True
if i == 0:
if 1 not in stones:
return False
else:
mem[(0, 1)] = dp(1, 1, mem)
return mem[(0, 1)]
if k == 1:
if (i+2) not in stones and (i+1) not in stones:
mem[(i, k)] = False
return False
elif (i+2) not in stones:
mem[(i, k)] = dp(i+1, 1, mem)
return mem[(i, k)]
elif (i+1) not in stones:
mem[(i, k)] = dp(i+2, 2, mem)
return mem[(i, k)]
else:
mem[(i, k)] = dp(i+1, 1, mem) or dp(i+2, 2, mem)
return mem[(i, k)]
else:
if (i+k+1) not in stones and (i+k) not in stones and (i+k-1) not in stones:
mem[(i, k)] = False
return False
elif (i+k+1) not in stones and (i+k) not in stones:
mem[(i, k)] = dp(i+k-1, k-1, mem)
return mem[(i, k)]
elif (i+k+1) not in stones and (i+k-1) not in stones:
mem[(i, k)] = dp(i+k, k, mem)
return mem[(i, k)]
elif (i+k) not in stones and (i+k-1) not in stones:
mem[(i, k)] = dp(i+k+1, k+1, mem)
return mem[(i, k)]
elif (i+k+1) not in stones:
mem[(i, k)] = dp(i+k, k, mem) or dp(i+k-1, k-1, mem)
return mem[(i, k)]
elif (i+k) not in stones:
mem[(i, k)] = dp(i+k+1, k+1, mem) or dp(i+k-1, k-1, mem)
return mem[(i, k)]
elif (i+k-1) not in stones:
mem[(i, k)] = dp(i+k+1, k+1, mem) or dp(i+k, k, mem)
return mem[(i, k)]
else:
mem[(i, k)] = dp(i+k+1, k+1, mem) or dp(i+k, k, mem) or dp(i+k-1, k-1, mem)
return mem[(i, k)]
mem = {}
return dp(0, 1, mem)
``````

• Cool, but isn't a bit too verbose for Python? Here's essentially the same thing:

``````if stones[1] != 1:
return False
stones_set = set(stones)
known = {}
def canCross(s1, s2):
if (s1, s2) not in known:
if s2 == stones[-1]:
known[(s1, s2)] = True
else:
d = s2 - s1
known[(s1, s2)] = any(canCross(s2, s3) for s3
in xrange(s2 + d - 1 if d > 1 else s2 + d, s2 + d + 2)
if s3 in stones_set)
return known[(s1, s2)]
return canCross(0, 1)
``````

Accepted, but fails on my PC: maximum recursion depth exceeded. But then again, so does your solution. Guess this approach doesn't work well with Python.

• @SergeyTachenov It is. I was rushing it. Do u mind pasting the test-case where it overflew? Thx a lot!

• Just in case you didn't know, `known[(s1, s2)]` is the same as `known[s1, s2]`.

• @AlgoGuruZ It's a bit too long to paste, but it just goes 0, 1, 2... 999. Calling `sys.setrecursionlimit(5000)` fixed it, though.

@StefanPochmann I always confuse when parentheses are needed and when not. Just like I always use parentheses in C++ and Java around `>> <<` and `& | ^`. But in this case it should've been obvious. I don't feel bad about it, though, as it makes the whole thing more explicit. I'm more worried about that ugly `s2 + d - 1 if d > 1 else s2 + d` part and the `if stones[1] != 1` case, but I can't figure out how to get rid of them in an elegant way.

• I think I got it now:

``````stones_set = set(stones)
known = {}
def canCross(s1, s2):
if (s1, s2) not in known:
if s2 == stones[-1]:
known[s1, s2] = True
else:
d2 = s2 - s1
known[s1, s2] = any(canCross(s2, s2 + d3) for d3
in xrange(max(d2 - 1, 1), d2 + 2)
if s2 + d3 in stones_set)
return known[s1, s2]
return canCross(0, 0)
``````

No more that ugly special case, and `max` certainly looks better than that ugly `if`.

Fun fact: using `xrange(d2 + 1, max(d2 - 2, 0), -1)` instead improves the run time to about 70 ms (from about 100). Guess that's because it uses long jumps when possible, therefore reaching the target earlier.

• @SergeyTachenov Nice improvements. You could also directly `return True` and then you don't need the `else` and can unindent its contents.

I disagree that `known[(s1, s2)]` is more "explicit" than `known[s1, s2]`. That makes it sound like the latter has implicit parentheses. To quote the Python Wiki, "it is the comma, not the parentheses, that define the tuple" (though it's talking about other cases). Parentheses are not essential for tuples (except for the empty tuple `()`), they're just sometimes needed for grouping. Just like they're sometimes needed for grouping other things, e.g., `(i + j) * n`. Would you also use `known[(i + j)]` instead of `known[i + j]` and call the former more explicit?

Edit: The docs also say "Note that tuples are not formed by the parentheses, but rather by use of the comma operator. The exception is the empty tuple".

• @StefanPochmann You mean like this?

``````if s2 == stones[-1]:
return True
if (s1, s2) not in known:
d2 = s2 - s1
known[s1, s2] = any(canCross(s2, s2 + d3) for d3
in xrange(d2 + 1, max(d2 - 2, 0), -1)
if s2 + d3 in stones_set)
``````

Yeah, I have read that stuff about tuples. But I still find it confusing and because of that often add parentheses needlessly without giving it a second thought.

• @SergeyTachenov Yeah, like that or with the `if s2 == stones[-1]: return True` still inside the other `if`. Not sure what's better.

• @StefanPochmann I don't see a point in putting it in the other `if`. If we're going to return `True` without memoizing it anyway, why bother checking that the answer is not memoized yet?

• @SergeyTachenov It would be faster. Outside, that check will be done at every single call during the search, even on "repeated calls". Inside, it would be done less often.

• @StefanPochmann Oh, I hadn't thought of that. Tried to submitting, it doesn't seem there's any difference. Both variants run in about 190 ms (some tests were added, so it's slower now). Interestingly, the variant without the extra `return` is slightly faster: 160-170 ms. Maybe within margin of error, although I submitted three times.

• @SergeyTachenov Yeah, I wouldn't expect it to be noticeable in the OJ. I now tested locally, testing each version three times 100 times on `range(1999) + [9999]` (that's a case where the inside-vs-outside should play a role, as there are relatively many repeated calls and we must do the full search because there's no way the frog can cross):

``````from timeit import timeit
for _ in range(3):
print timeit(lambda: Solution().canCross(range(1999) + [9999]), number=100)
``````

With `if s2 == stones[-1]: return True` inside the other `if` (times in seconds):
18.5091165364
18.4510093963
18.6512655162

Outside the other `if`:
18.8030853982
18.9244283874
18.9133609044

With `known[s1, s2] = True` and `else`:
18.483076973
18.6257707035
18.4797243375

The "outside"-version looks consistently slower, as expected. The other two look about equally fast.

• @StefanPochmann Wow, you must have some impressive hardware. Or use some optimization settings. Here are my results:

Inside:
32.6581707025
32.9920321176
33.2971709571

Outside:
33.6750903148
34.3595633396
34.756462441

If-else:
32.8538324421
33.6187497321
33.2839616224

And here's a bonus surprise. Bottom-up:
12.0656952994
12.1085436985
12.0477046521

I guess that bottom-up is more efficient in general, but is slower in the OJ because most OJ test cases are positive, where top-down approach works better because of its DFS nature.

• @SergeyTachenov Well I have an i7-6700, that's fairly fast, yes :-). What's the bottom-up code you tested?

• @StefanPochmann The second solution from my post.

• I have a question. Where is the redundancy coming from? Or someone can give me an example of this redundancy.

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