Manhattan, New York, NY is a very orga$-$

nized city so walking in the streets is easy. We can think of the road network

as an n$-$by$-$n square board. Imagine that your initial position is $(0,0)$ and you

want to reach your destination at position $($n$,$ n$).$ You are allowed only to move

right or up and you cannot leave the board. Moreover at all times, your x

coordinate should be larger or equal to the y coordinate $($you never cross the

diagonal$).$ Design a dynamic programming algorithm that computes the num$-$

ber of possible ways to reach your destination.

For example, for n $=4,$ in Figure $2$ you can see two possible paths $($green

and blue lines, with orange we have the diagonal that we cannot cross$).$ In total

there are $14$ ways $($count them and convince yourself$).$