Graphtheory. How to approach these kinds of proble

问题:

Find the number of paths on the Cartesian plane from (0, 0) to (n, n), which never raises above the y = x line. It is possible to make three types of moves along the path:

move up, i.e. from (i, j) to (i, j + 1);
move to the right, i.e. from (i, j) to (i + 1, j);
the right-up move, i.e. from (i, j) to (i + 1, j + 1)

回答1:

Path count 101

First, we solve a simpler problem:

Find the number of paths on the Cartesian plane from (0, 0) to (n, n) with:

• move up, i.e. from (i, j) to (i, j + 1);
• move to the right, i.e. from (i, j) to (i + 1, j);

and we can go to grid which x < y.

How to solve it? Too Hard? Okay, we try to find the number of paths from (0, 0) to (2, 2) first. We could draw all paths in a grid:

We define

f(x,y) => the number of paths from (0, 0) to (x, y)

You can see the path to (2, 2) from either (1, 2) or (1, 2), so we can get:

f(2, 2) = f(2, 1) + f(1, 2)

And then you will notice for point(x, y), its path from either (x, y - 1) or (x - 1, y). That's very natural, since we have only two possible moves:

• move up, i.e. from (i, j) to (i, j + 1);
• move to the right, i.e. from (i, j) to (i + 1, j);

I draw a larger illustration for you, and you can check our conclusion:

So we can get that:

f(x, y) = f(x, y - 1) + f(x - 1, y)

Wait... What if x = 0 or y = 0? That's quite direct:

if x = 0 => f(x, y) = f(x, y - 1)
if y = 0 => f(x, y) = f(x - 1, y)

The last... How about f(0, 0)? We define:

f(0, 0) = 1

since there just 1 path from (0,0) to (1,0) and (0, 1).

OK, summarise:

f(x, y) = f(x, y - 1) + f(x - 1, y)
if x = 0 => f(x, y) = f(x, y - 1)
if y = 0 => f(x, y) = f(x - 1, y)
f(0, 0) = 1

And by recursion, we can solve that problem.

---

Your problem

Now let's discuss your original problem, just modify our equations a little bit:

f(x, y) = f(x, y - 1) + f(x - 1, y) + f(x - 1, y - 1)
if x = 0 => f(x, y) = f(x, y - 1)
if y = 0 => f(x, y) = f(x - 1, y)
if x < y => f(x, y) = 0
f(0, 0) = 1

and it will result my code.

The last thing I add to my code is Memoization. In short, Memoization can eliminate the repeat calculation -- if we have calculated f(x,y) already, just store it in a dictionary and never calculate it again. You can read the wiki page for a further learning.

So, that's all of my code. If you still get some questions, you can leave a comment here, and I will reply it as soon as possible.

Code:

d = {}  # Memoization


def find(x, y):
    if x == 0 and y == 0:
        return 1
    if x < y:
        return 0
    if d.get((x, y)) is not None:
        return d.get((x, y))
    ret = 0
    if x > 0:
        ret += find(x - 1, y)
    if y > 0:
        ret += find(x, y - 1)
    if x > 0 and y > 0:
        ret += find(x - 1, y - 1)
    d[(x, y)] = ret
    return ret


print find(2, 1) # 4

回答2:

For additional ideas for solving problems such as this one, there is a mathematical curiosity that is in 1-1 correspondence with not only the sequences produced by lattice walks where one's steps must remain below the line x = y, but a veritable plethora, of fantastical mathematical beasts that cut a wide swath of applicability to problem solving and research.

What are these curiosities? Catalan Numbers:

C_n = 1/(n+1)*(2n)Choose(n), n >= 0, where if n = 0, C_0 = 1.

They also count:

1. The number of expressions containing $n$ pairs of parentheses
   • eg. n = 3: ((())), (()()), (())(), ()(()), ()()()
2. Number of plane trees with n + 1 vertices
3. Number of Triangulations of a convex (n + 2)-gon
4. Monomials from the product: p(x1, ..., xn) = x1(x1 + x2)(x1 + x2 + x3) ... (x1 + ... + xn)
5. bipartite vertices of rooted planar trees
6. And soooo many more things

These object appear in a lot of active research in mathematical physics, for instance, which is an active area of algorithms research due to the enormous data sets.

So you never know what seemingly far flung concepts are intimately linked in some deep dark mathematical recess.