Project Euler #15

Solution 1:

Quick No Programming Solution (based on combinatorics)

I take it "no backtracking" means we always either increase x or increase y.

If so, we know that in total we will have 40 steps to reach the finish -- 20 increases in x, 20 increases in y.

The only question is which of the 40 are the 20 increases in x. The problem amounts to: how many different ways can you choose 20 elements out of a set of 40 elements. (The elements are: step 1, step 2, etc. and we're choosing, say, the ones that are increases in x).

There's a formula for this: it's the binomial coefficient with 40 on top and 20 on the bottom. The formula is 40!/((20!)(40-20)!), in other words 40!/(20!)^2. Here ! represents factorial. (e.g., 5! = 5*4*3*2*1)

Canceling out one of the 20! and part of the 40!, this becomes: (40*39*38*37*36*35*34*33*32*31*30*29*28*27*26*25*24*23*22*21)/(20*19*18*17*16*15*14*13*12*11*10*9*8*7*6*5*4*3*2*1). The problem is thus reduced to simple arithmatic. The answer is 137,846,528,820.

For comparison, note that (4*3)/(2*1) gives the answer from their example, 6.

Solution 2:

This can be done much faster if you use dynamic programming (storing the results of subproblems rather than recomputing them). Dynamic programming can be applied to problems that exhibit optimal substructure - this means that an optimal solution can be constructed from optimal solutions to subproblems (credit Wikipedia).

I'd rather not give away the answer, but consider how the number of paths to the lower right corner may be related to the number of paths to adjacent squares.

Also - if you were going to work this out by hand, how would you do it?