图论。如何解决这类问题？我想知道在尝试解决此问题时需要思考的逻辑和方式。 [英] 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.
问题描述
在笛卡尔平面上找到从（0，0）到（n，n）的路径数，该路径数永远不会超过y = x线。可以沿着路径进行三种类型的移动：
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)
推荐答案
路径计数101
首先，我们解决一个简单的问题：
Path count 101
First, we solve a simpler problem:
用以下方法查找笛卡尔平面上从（0，0）到（n，n）的路径数：
Find the number of paths on the Cartesian plane from (0, 0) to (n, n) with:
- 向上移动，即从（i，j）移至（i，j + 1）；
- 向右移动，即从（i，j）移至（i + 1， j）;
，我们可以进入x < y。
and we can go to grid which x < y.
如何解决？太难？好的，我们尝试首先找到从（0，0）到（2，2）的路径数。我们可以在网格中绘制所有路径：
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:
我们定义
f(x,y) => the number of paths from (0, 0) to (x, y)
您可以看到路径从（1、2）或（1、2）转换为（2、2），所以我们可以得到：
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)
您会注意到point（x，y）从（x，y-1）或（x-1，y）的路径。这很自然，因为我们只有两种可能的移动方式：
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:
- 向上移动，即从（i，j）移至（i，j + 1）;
- 向右移动，即从（i，j）移至（i + 1，j）；
我为您绘制了一个较大的插图，您可以检查我们的结论：
I draw a larger illustration for you, and you can check our conclusion:
所以我们可以得到：
f(x, y) = f(x, y - 1) + f(x - 1, y)
等等。 。如果x = 0或y = 0怎么办？这很直接：
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)
最后一个...如何大约f（0，0）？我们定义：
The last... How about f(0, 0)? We define:
f(0, 0) = 1
因为从（0,0）到（1,0）和（0，1）只有1条路径。
since there just 1 path from (0,0) to (1,0) and (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
通过递归，我们可以解决这个问题。
And by recursion, we can solve that 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
会得到我的代码。
我添加到代码中的最后一件事是记忆力。简而言之，记忆化可以消除重复计算-如果我们已经计算了f（x，y），只需将其存储在字典中就不再计算。您可以阅读Wiki页面以进行进一步的学习。
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.
代码：
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
这篇关于图论。如何解决这类问题？我想知道在尝试解决此问题时需要思考的逻辑和方式。的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
