The DP idea — compare matrix-path-counter and EditDistance

- showcasing efficient queue in python.
- showcasing using (x,y) coordinates as dictionary key
- showcasing find max value in a dictionary

–Requirement: (https://leetcode.com/problems/unique-paths-ii/description/ is similar)

See Q9.pdf in the email to Ashish. Here are some key points:

Consider a maze mapped to a matrix with an upper left corner at coordinates (row, column) = (0, 0). Any movement must be in increasing row or column direction. You must determine the number of distinct paths through the maze. You will always start at position (0, 0), the top left, and end up at (max(row), max(column)), the bottom right.

1 1 0 1

1 1 1 1

As an example, consider the above matrix where 1 indicates an open cell and 0 indicates blocked. You can only travel through open cells, so no path can go through the cell at (0, 2). There are two distinct paths to the goal. As a 2nd example, matrix below has 10 paths:

1 1 1 1

1 1 1 1

1 1 1 1

https://github.com/tiger40490/repo1/blob/py1/py/2d/classic_pathCountQ9.py is my solution.

==== Analysis ====

I see a binary tree, where each node is a cell. Cell (0,0) has down/left node (1,0) + right node (0,1). I feel this is similar to a more generic problem “count paths between 2 nodes in a binary tree”

–DFT:

😦 I implemented something like a DFT but it was too slow with some test cases

😦 can overflow stack

🙂 DFT can print each unique path. I think BFT can’t.

🙂 DFT is easier to implement than BFT

–DynamicProgramming BFT solution from origin, as I described to Bill Pinsky:

This solution is more versatile than the one from Ashish. It can handle any directed graph.

Mark each node as “computed” once we have computed a score denoting how many paths-from-root there are. Save the score in a shadow matrix.

Origin node has score 1. Blocked cell has score 0.

Start BFT from origin. The two immediate neighbors are set to 1 (or 0 if blocked). Every node can be computed by adding up above-score + left-score. (This algo is simpler than the EditDistance algo.)

Performance Keynote — My implementation was extremely slow (albeit correct) until I added an “if already computed, then continue” early in the loop

Q: why is score[1,1] accessed 4 times?

A: node[1,1] is added to the queue twice. Each dequeue would need one check.

A: Also score[1,2] need to access score[1,1] as a parent. Ditto score[2,1]

–Ashish Singh gave me a much simpler solution, as shown in my github code.