test suite
Standard advice in any language: Include an automated test suite with your target code. How do we know the code you write isn't 100% perfect all the time? Because you're posting a request for help. Plus, you're human. Making it easy for strangers to run your code means it will be easy for you to run your code when you revisit it next year.
Standard advice for python language: Avoid nesting defs.
Why? Other than the whole global variable coupling thing? Because they make it very difficult for a subsequent maintenance engineer to come along and write missing unit tests -- the nested functions are inaccessible.
lint
memoKey = [row, col] Pep-8 asks that you name it memo_key.
On first reading I thought you intended a (row, col) tuple instead. But it turns out this is a fancier datastructure than that. Its format needs to be documented.
solution
I understand that the problem statement merely asks for "number of platforms". Still, it makes me sad that after laboriously computing 21 we still can't recover that nice 123...jkl path diagram we see in OP. Consider changing your API to export the winning path.
It seems like this could have a positive effect on how instructive a test suite is, and on time to debug issues after attempting a refactor.
spurious comment
if row == len(grid) - 1: # Reached the bottom Well, actually this is kind of helpful. But I wish it wasn't, that is, I wish there was no need for it. Prefer to define width, height temp variables so the code explains itself.
docstring
Your depth first search routine doesn't have one. Nor does longest_path, nor the module. Nor did you include any helpful # comments describing the memo key.
Maybe you feel your code is self explanatory, and it reads as cleanly as sonnet 18. I beg to differ. What I'm specifically looking for is invariants and representations. We're doing DP here, cool. But tell me how you're remembering results so we needn't re-compute them, describe the plan, the datastructure. I see three .append()'s of a pair, but the meaning of pair[0] and pair[1] are not self-evident upon first reading.
I store the state of the cell to the left and right to prevent visiting a platform twice.
Good. Now expand on that. In the source code, where it will be available to a maintenance engineer some months down the road.
Or consider making a memo of (row, col) in a set, which we consult during planning so we don't make a prohibited move.
This seems tedious:
if col == 0: memoKey.append(('#', grid[row][1])) elif col == len(grid[0]) - 1: memoKey.append((grid[row][col - 1], '#')) else: memoKey.append((grid[row][col - 1], grid[row][col + 1])) Consider pre-processing the input map to add '#' boundary lines around it, for example on the left and right walls. It's unclear why we're checking col for out-of-bounds, but not row. I am left wondering: Why is horizontal travel special, why is it handled differently from vertical travel?
OIC. Re-reading the problem statement, there's a requirement that Y coordinate be monotonic, we can go down but never up. Hmmm.
directions = [(0, 1), (1, 0), (0, -1)] # Right, Down, Left Thank you for those (dy, dx) pairs, that's brilliant, very helpful. The logic testing for whether new row,col is feasible is quite clear.
# Mark the current cell as visited grid[row][col] = '#' nit: IDK, maybe choose an alternate character, such as @, to distinguish between "this was impassable from the outset" and "this is currently impassable due to being visited". Which would trivially change any == '#' tests into != '.'. I'm just looking for more informative debugging sessions, is all.
algorithm
Sooo, here's the aspect of the current DFS that I'm dissatisfied with. Imagine the bottom portion of the maze is boring switchbacks that keep taking us from left margin to right, back to left, back to right, eventually we exit at the bottom. And the top of the maze is pretty free, only a few obstacles, many starting paths. So we will be forced to begin with one of those paths, and then we spend a lot of time traversing those boring switchbacks. Then we try another of those paths, plus switchbacks. Yeah, I'm getting tired of the switchbacks, they're time consuming, and the maze fundamentally just isn't all that hard.
Let's exploit the "no going up!" rule, recursively. Consider a single-row maze -- the bottom row. We will pretend there is an imaginary row of just '.' platforms above it, so we could enter the row from any column position.
Now we have a very simple problem. For entry at any of the column positions, report the maximum possible value, and memoize those results.
Now go up a row, and for all column positions try to maximize the value of L/R traversal within the row plus the memoized value of exiting downward.
Repeat till all rows are consumed.