I've been pondering about this algorithm for about a week but I'm still

not able to write a "fast" working method/algorithm to solve the Number-of-paths-exercise we were

given in my class />

**so here's the task:**

Write an efficient java program "Paths" which solves the following task:

- Read input n ∈ N and give output a(n) which is the number of paths from (0,0) to (n,0)

it is not allowed to go over the diagonal (m,m) and also not below the x-axis (m,0)

here are the allowed steps:

**u**= (1,1),

**U**= (1,4),

**d**= (1,−1),

**D**= (1,−4) and

**H**= (1,0)

steps are performed in a two-dimensional-coordinate-system!

Well don't get me wrong, I may be new here and the first thing I do is asking to solve an exercise, but

I'm pretty much "new" to such exercises. I'm studying Software Engineering atm for 1.5years but we never talked about

programming algorithms and I never faced the problem that my code is not efficient enough.

I already made some guesses, maybe they're useful to build this program.

Thinking about the paths and the steps you are allowed to perform I decided to first draw some examples.

I used some tiny numbers like 3, 4, 5 hoping to find a sheme...

The next idea was to get "all" steps possible and erase the one which go beyond the allowed area like

building a binary truthtable with lets say five inputs which represent the steps.

But for now I don't really know where to start. I mean i cannot start programming unless I managed to

find a fitting, working, efficient algorithm for n=1000 or sth. like that.

I hope there's someone out there who is familiar with algorithms />

Thanks alot guys!