# Dynamic Programming - Print all paths from (0,0) to (n,n) in Grid/Lattice

I'm trying to write an algorithm to print all the paths from point (0,0) to (n,n) in a grid.
The only possible moves are right and up.
Also, you can't move below the diagonal y=x. e.g if you're at (1,1) you can only move to (1,2), but not to (2,1), since it's below the y=x diagonal.

I wrote an algorithm that calculates the number of possible paths from (0,0) to any given (x,y), such that the above limitations are held, but I can't find a way to print out the paths that give these numbers.

The algorithm I wrote is a bottom-up one, as follows:

JUMP(x, y)
1.  M[x-1,y+1] ← 1
2.  for i=0 to x+1
M[i,y+1] ← 0
3.  for i=0 to y+1
M[x+1,i] ← 0
4.  for j=0 to y-1
for i=j+1 to x
M[i,j] ← 0

5.  for j=y to 0
for i=j to 0
M[i,j] ← M[i+1,j] + M[i,j+1]

6.  return M[i,j]


• Printing all paths is often a bad idea (w.r.t. resources) but here's a hint: after filling the table, retrace the steps you've taken. – Raphael Jan 14 '15 at 17:40
• The number of paths is given by the Catalan numbers. – Yuval Filmus Jan 14 '15 at 20:58
• @YuvalFilmus I know how to get the number of paths (both via a top-down approach as well as a bottom-up one), and that's covered pretty nicely online. The problem is when trying to print out all the paths that get you from point A to point B, which I can't seem to be able to wrap my head around on. – The_Ben Jan 14 '15 at 22:57
• @Raphael Retracing one paths back is pretty simple as well, as you can just save a general pi array of size n*n and trace your way "back" from (n,n) to (0,0) using it. However, printing all the paths from (0,0) to (n,n) is the hard part here. – The_Ben Jan 14 '15 at 22:59
• @The_Ben The technique for printing one path can be extended to print all paths. Note that using DP for this task is unnecessary; its power lies in not examining all solutions. Just do DFS with backtracking or something similar. – Raphael Jan 15 '15 at 8:01

You can solve this problem using a recursive formulation of print all paths from a point $(i,j)$ to the target $(n,n)$ in the grid. I call this function $f(i,j)$. So the all paths will be in $f(0,0)$ call.

$f(i,j) = \begin{cases} \emptyset & if\ \ {i>j}\\ \emptyset & if\ \ \neg( {0\leq i\leq n\ \wedge 0\leq j\leq n) }\\ \{(n,n)\} & if \ \ i = n \wedge j = n\\ \bigcup_{p\,\in\, f(i+1,j)\,\cup\,f(i,j+1) } \ \ \{(i,j)\}\cup p & \text{otherwise} \end{cases}$

By example, two of all paths from $f(0,0)$ when $n=4$ are:

blue path = {{0, 0}, {0, 1}, {1, 1}, {1, 2}, {2, 2}, {2, 3}, {3, 3}, {3, 4}, {4, 4}}

red path = {{0, 0}, {0, 1}, {0, 2}, {1, 2}, {1, 3}, {2, 3}, {2, 4}, {3, 4}, {4, 4}}

So, although programming is not in the scope of this site, I think is good to see a implementation for a memoization version of the above algorithm. asdf

from functools import wraps

def memo(func):
cache = {}

@wraps(func)
def wrap(*args):
if args not in cache:
cache[args] = func(*args)
return cache[args]
return wrap

@memo
def f(i, j):
global n
if i > j:
return []
if not (0 <= i <= n and 0 <= j <= n):
return []
if i == n and j == n:
return [[(n,n)]]
alls = []
for path in f(i, j+1)+f(i+1, j):
if len(path) > 0:
alls += [[(i,j)] + path]
return alls

n = 4
for path in f(0,0):
print path

• Thank you very much. This seems to be a good solution, but what is the time complexity of it? Isn't it O(2^(n*n))? Seems a bit high when doing this recursively. Also, do you know of any bottom-up approach to solve this (rather than top-down like you did above, with memoization). – The_Ben Jan 14 '15 at 22:54
• You seem to be right about complexity, btw generate all paths is usually expensive for graphs, like in this case, your lattice. And, for a bottom-up approach, may be you can do a Breath First Search in the lattice asserting all conditions about monotonic paths. – jonaprieto Jan 14 '15 at 23:12

In the case of an $x$ by $y$ grid (assuming we start at the bottom-left and travel toward the upper-right), you can notice that every possible path will always contain $x$ steps toward the right and $y$ steps upward. You could encode every possible path with a binary string of length $x+y$ where $0$ encodes "right" and $1$ encodes "up", and there are exactly $x$ $0$'s and exactly $y$ $1$'s in the string.

To solve the problem, you could follow this procedure:

• take a binary string of length $x+y$, starting with all $0$'s
• check if the string has $y$ bits equal to $1$
• if so, print the path the string represents, with $0$ = "right" and $1$ = "up"
• incrememt the binary string by $1$ and repeat

In pseudocode:

x = 7; //the grid is x by y in size
y = 9;
N = x+y; //length of the binary string

for i from 0 to (2^N)-1:
if NumberOfOnes(i,N) == y:
PrintPath(i,N);


To check if the least-significant bit is a 1, we can just take i mod 2 and check if the result is a 1. We can check bit j in the same way just by bit-shifting j bits to to the right and repeating the processes.

function NumberOfOnes(i,N)
ones = 0;
zeroes = 0;
bit = 0;
for j from N-1 to 0
temp = i >> j;     //ensures we read the string from left-to-right
if (temp mod 2) == 1
ones++
else
zeros++
if zeros > ones  // this protects us from moving below the diagonal
ones = -1;
break;
return ones


To print the string we use a similar process to find the 1's and let 0 mean "right" and 1 mean "up". We also need to read the string left-to-right.

function PrintPath(i,N)
path_string = [empty]
for j from N-1 to 0
temp = i >> j          //ensures we read the string left-to-right
if (temp mod 2) == 1
path_string += 'up, '
else
path_string += 'right, '

print(path_string)


This involves checking $2^{x+y}$ binary numbers and performing $x+y$ bit-shifts on each one.

Also for counting the paths, you can notice that the number of acceptable binary strings is just ${x + y \choose y}/2$ since we have $x+y$ binary digits and need to choose $y$ of them to be $1$, and divide by $2$ to ignore paths below the diagonal.

• For $x=y=3$ this will print (simplifying a bit) URRURU, but that wouldn't be allowed, since the OP stated that no paths can be below the main diagonal. – Rick Decker Jan 15 '15 at 19:48
• @RickDecker--good point. I added some extra code NumberOfOnes() to ignore these cases and some code in PrintPath() to read the string in the proper direction. – eigenchris Jan 15 '15 at 19:51
• @eigenchris This seems like it would work, but kind of "runs around the whole idea", doesn't it? I mean, you're solving an equivalent problem, but not the same problem. I need to use dynamic programming here, which your suggested solution isn't written by (this is an interview question). – The_Ben Jan 16 '15 at 18:57
• @The_Ben I didn't realize you were constrained to use dynamic programming. It's true that my solution is very specific to this problem and doesn't follow any sort of general bottom-up or top-down approach you would use to tackle algorithm problems in general, so it's not very instructional in that sense. However my solution has $O(2^{2n})$ complexity so I thought it would be worth mentioning. – eigenchris Jan 16 '15 at 19:32
• @The_Ben As Raphael has pointed out, DP represents a scheme to intelligently reuse interim results in an optimization setting. There is nothing to optimize here as you are requested - in sloppy phrasing - to enumerate the complete search space. So you might have been asked a trick question. – collapsar Jan 16 '15 at 19:37