Graphtheory.如何处理这些问题？我想知道在尝试解决这个问题时需要思考的逻辑和方式.

Question

求出笛卡尔平面上从(0,0)到(n,n)的路径数,它们永远不会超过y = x线.沿着路径可以进行三种类型的移动:

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)

Answer 1

路径计数101

首先,我们解决一个更简单的问题:

通过以下方式查找笛卡尔平面上从(0,0)到(n,n)的路径数:

• 向上移动,即从(i,j)到(i,j + 1);
• 向右移动,即从(i,j)到(i + 1,j);

我们可以去x <y的网格.

怎么解决？太难？好的,我们首先尝试找到从(0,0)到(2,2)的路径数.我们可以在网格中绘制所有路径:

我们定义

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

你可以从(1,2)或(1,2)看到(2,2)的路径,所以我们可以得到:

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

然后你会注意到点(x,y),它的路径来自(x,y - 1)或(x - 1,y).这很自然,因为我们只有两个可能的举动:

• 向上移动,即从(i,j)到(i,j + 1);
• 向右移动,即从(i,j)到(i + 1,j);

我为您绘制了一个更大的插图,您可以查看我们的结论:

所以我们可以得到:

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

等等......如果x = 0或y = 0怎么办？这很直接:

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

最后...... f(0,0)怎么样？我们定义:

f(0, 0) = 1

因为从(0,0)到(1,0)和(0,1)只有一条路径.

好的,总结一下:

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

通过递归,我们可以解决这个问题.

你的问题

现在让我们讨论你的原始问题,只需修改我们的方程式:

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

它会导致我的代码.

我添加到代码中的最后一件事是Memoization.简而言之,Memoization可以消除重复计算 - 如果我们已经计算了f(x,y),只需将其存储在字典中,而不再计算它.您可以阅读维基页面以获得进一步的学习.

所以,这就是我的所有代码.如果您仍然有问题,可以在这里发表评论,我会尽快回复.

码:

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