图论。如何处理这类问题？我想知道在尝试解决此问题时需要思考的逻辑和方式。

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

因为只有 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)，只需将其存储在字典中，不再计算。您可以阅读 wiki 页面以进一步学习。

所以，这就是我的全部代码。如果还有什么问题，可以在这里留言，我会尽快回复。

代码：

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

Answer 2

对于解决此类问题的其他想法，有一种数学上的好奇心，它不仅与格子行走产生的序列一一对应，其中一个人的步数必须保持在 x = y 线以下，而且名副其实的大量奇异的数学怪兽，它们在解决问题和研究方面具有广泛的适用性。

这些好奇心是什么？ Catalan Numbers:

C_n = 1/(n+1)*(2n)选择(n), n >= 0, 其中如果 n = 0, C_0 = 1.

他们也算：

包含$n$对括号的表达式的数量
- 例如。 n = 3: ((())), (()()), (())(), ()(()), ()()()
有n+1个顶点的梧桐树数量
凸 (n + 2)-gon 的三角剖分数
乘积的单项式：p(x1, ..., xn) = x1(x1 + x2)(x1 + x2 + x3) ... (x1 + ... + xn)
有根平面树的二分顶点
还有很多东西

这些对象出现在数学物理学的许多活跃研究中，例如，由于庞大的数据集，这是算法研究的一个活跃领域。

所以你永远不知道在一些深奥的数学隐蔽处，哪些看似遥远的概念是紧密联系在一起的。

图论。如何处理这类问题？我想知道在尝试解决此问题时需要思考的逻辑和方式。

Graphtheory. How to approach these kinds of problems? I want to know the logic and the way one needs to think while trying to solve this.

dynamic-programming

graph-algorithm

python-2.7

路径数 101

你的问题