欧拉项目是一系列令人兴奋的编程问题，通常具有数学背景。 这些问题通常以必须开发复杂算法的方式提出，以便在合理的时间内达到目标。 今天，我们解决了问题15：晶格路径，您可以使用简单的组合方法找到其解决方案。
问题如下:
„Starting in the top left corner of a 2×2 grid, and only being able to move to the right and down, there are exactly 6 routes to the bottom right corner. How many such routes are there through a 20×20 grid?“
问题也可以用不同的方式表述：需要的是所有路径的子集的功能
$$W = {w_1, …, w_{2^n}}, \, w_k = p_1 \cdots p_{2\cdot n}, \, p_k \in \{ R, D \}.$$
这是一个简单的组合问题，其中我们使用urn模型（无需替换，也无需考虑顺序）。 现在，我们对它保持\(R\)和\(D\)完全相同的频率\(D\)路径感兴趣。 这导致所有可能的组合:
$$\binom{2\cdot n}{n} = \frac{(2\cdot n)!}{n!\cdot n!}$$
对于\(n=20\)我们得到:
$$ \frac{(40)!}{20!\cdot 20!} = 137846528820.$$
我们可以将问题扩展到非正方形网格。 以下解决方案在bcmath的帮助下以运行时间为\( O(n) \)和输入格式为“测试用例的数量\(n_1\) \(m_1\) ，...”在PHP中实现计算。:
47bb78215ee0531a787bb5034652eaf4
顺便说一下，欧拉项目的所有问题也可以在推荐的HackerRank网站上在线解决。