 <p>While dynamic programming is certainly a correct way to solve this kind of problems, this particular instance shows a regularity that can be exploited. </p> <p>You can see the problem as arranging a number of “right"s and “down"s, being wary not to count multiple times identical arrangements.<br> For example, the solutions of the size 2 problem (reported in the images in the question) can be see this way:</p> <pre><code>→→↓↓ →↓→↓ →↓↓→ ↓→→↓ ↓→↓→ ↓↓→→ </code></pre> <p>So, for any grid of side n, you can find the solution by means of <a href="http://en.wikipedia.org/wiki/Combinatorics" rel="nofollow noreferrer">combinatorics</a>:</p> <pre><code>from math import factorial n = 20 print factorial(2*n)/(factorial(n)*factorial(n)) </code></pre> <p>2n! is the number of arrangements of the 20 → + 20↓, while the two n! account for the identical ways in which the → and ↓ can be arranged. </p>