欧拉项目＃15
昨天晚上，我试图解决欧拉项目的第15项挑战 ：
从2×2网格的左上angular开始，右下angular有6条路线（没有回溯）。
替代文字http://projecteuler.net/projecthttp://img.dovov.comp_015.gif
通过20×20网格有多less路线？
我觉得这不应该这么难，所以我写了一个基本的recursion函数：
const int gridSize = 20; // call with progress(0, 0) static int progress(int x, int y) { int i = 0; if (x < gridSize) i += progress(x + 1, y); if (y < gridSize) i += progress(x, y + 1); if (x == gridSize && y == gridSize) return 1; return i; } 我validation了它适用于较小的网格（如2×2或3×3），然后将其设置为运行20×20网格。 想象一下，当5个小时后，程序仍然愉快地处理数据，只有大约80％完成了（基于检查其在电网中的当前位置/路线），我感到惊讶。
很明显，我正在走错这个方向。 你将如何解决这个问题？ 我认为应该使用方程而不是像我的方法来解决，但不幸的是，这不是我的强项。
更新 ：
我现在有一个工作版本。 基本上它caching了在一个×m块仍然需要遍历之前得到的结果。 下面是代码以及一些评论：
// the size of our grid static int gridSize = 20; // the amount of paths available for a "NxM" block, eg "2x2" => 4 static Dictionary<string, long> pathsByBlock = new Dictionary<string, long>(); // calculate the surface of the block to the finish line static long calcsurface(long x, long y) { return (gridSize - x) * (gridSize - y); } // call using progress (0, 0) static long progress(long x, long y) { // first calculate the surface of the block remaining long surface = calcsurface(x, y); long i = 0; // zero surface means only 1 path remains // (we either go only right, or only down) if (surface == 0) return 1; // create a textual representation of the remaining // block, for use in the dictionary string block = (gridSize - x) + "x" + (gridSize - y); // if a same block has not been processed before if (!pathsByBlock.ContainsKey(block)) { // calculate it in the right direction if (x < gridSize) i += progress(x + 1, y); // and in the down direction if (y < gridSize) i += progress(x, y + 1); // and cache the result! pathsByBlock[block] = i; } // self-explanatory :) return pathsByBlock[block]; }
调用它20次，对于大小为1×1到20×20的网格，产生以下输出：
There are 2 paths in a 1 sized grid 0,0110006 seconds There are 6 paths in a 2 sized grid 0,0030002 seconds There are 20 paths in a 3 sized grid 0 seconds There are 70 paths in a 4 sized grid 0 seconds There are 252 paths in a 5 sized grid 0 seconds There are 924 paths in a 6 sized grid 0 seconds There are 3432 paths in a 7 sized grid 0 seconds There are 12870 paths in a 8 sized grid 0,001 seconds There are 48620 paths in a 9 sized grid 0,0010001 seconds There are 184756 paths in a 10 sized grid 0,001 seconds There are 705432 paths in a 11 sized grid 0 seconds There are 2704156 paths in a 12 sized grid 0 seconds There are 10400600 paths in a 13 sized grid 0,001 seconds There are 40116600 paths in a 14 sized grid 0 seconds There are 155117520 paths in a 15 sized grid 0 seconds There are 601080390 paths in a 16 sized grid 0,0010001 seconds There are 2333606220 paths in a 17 sized grid 0,001 seconds There are 9075135300 paths in a 18 sized grid 0,001 seconds There are 35345263800 paths in a 19 sized grid 0,001 seconds There are 137846528820 paths in a 20 sized grid 0,0010001 seconds 0,0390022 seconds in total
我接受了丹本的回答，因为他帮我find了这个解决scheme。 但也鼓励Tim Goodman和Agos 🙂
奖金更新 ：
在阅读Eric Lippert的回答之后，我又看了一遍，稍微改写了一下。 基本的想法还是一样的，但是caching部分已经被拿出来，放在一个单独的函数中，就像Eric的例子。 结果是一些更优雅的代码。
// the size of our grid const int gridSize = 20; // magic. static Func<A1, A2, R> Memoize<A1, A2, R>(this Func<A1, A2, R> f) { // Return a function which is f with caching. var dictionary = new Dictionary<string, R>(); return (A1 a1, A2 a2) => { R r; string key = a1 + "x" + a2; if (!dictionary.TryGetValue(key, out r)) { // not in cache yet r = f(a1, a2); dictionary.Add(key, r); } return r; }; } // calculate the surface of the block to the finish line static long calcsurface(long x, long y) { return (gridSize - x) * (gridSize - y); } // call using progress (0, 0) static Func<long, long, long> progress = ((Func<long, long, long>)((long x, long y) => { // first calculate the surface of the block remaining long surface = calcsurface(x, y); long i = 0; // zero surface means only 1 path remains // (we either go only right, or only down) if (surface == 0) return 1; // calculate it in the right direction if (x < gridSize) i += progress(x + 1, y); // and in the down direction if (y < gridSize) i += progress(x, y + 1); // self-explanatory :) return i; })).Memoize();
顺便说一句，我想不出一个更好的方法来使用这两个参数作为字典的关键。 我search了一下，似乎这是一个常见的解决scheme。 好吧。
如果使用dynamic编程 （存储子问题的结果而不是重新计算它们），这可以更快地完成。 dynamic规划可以应用于展现最优子结构的问题 – 这意味着可以从最优解到子问题（信用维基百科 ）构build最优解。
我宁愿不给出答案，但考虑到右下angular的path数量可能与相邻方块的path数量有关。
另外 – 如果你要用手工作，你会怎么做？
快速无编程解决scheme （基于组合）
我认为“不回溯”意味着我们总是增加x或增加y。
如果是这样，我们知道总共有40步到达结束–20次增加x，20次增加y。
唯一的问题是40中的哪一个是x的20次增加。 问题在于：有多less种不同的方法可以从一组40个元素中select20个元素。 （这些元素是：步骤1，步骤2等，我们正在select那些在x中增加的元素）。
有一个公式是这样的：二叉树系数在上面40，在下面20。 公式是40!/((20!)(40-20)!) ，换句话说40!/(20!)^2 。 这里! 代表阶乘。 （例如， 5! = 5*4*3*2*1 ）
取消20个之一！ (40*39*38*37*36*35*34*33*32*31*30*29*28*27*26*25*24*23*22*21)/(20*19*18*17*16*15*14*13*12*11*10*9*8*7*6*5*4*3*2*1)一部分变成： (40*39*38*37*36*35*34*33*32*31*30*29*28*27*26*25*24*23*22*21)/(20*19*18*17*16*15*14*13*12*11*10*9*8*7*6*5*4*3*2*1) 问题因此简化为简单的算术。 答案是137,846,528,820 。
为了比较，请注意(4*3)/(2*1)从他们的例子6给出答案。
正如其他人所指出的那样，这个特定的问题有一个离散的math解决scheme。 但是，假设你想要recursion地解决它。 你的性能问题是你一遍又一遍地解决同样的问题。
让我向你展示一个高阶的编程技巧，将会带来巨大的回报。 让我们来看一个更简单的recursion问题：
long Fib(n) { if (n < 2) return 1; return Fib(n-1) + Fib(n-2); }
你问这个来计算Fib（5）。 计算Fib（4）和Fib（3）。 计算Fib（4）计算Fib（3）和Fib（2）。 计算Fib（3）计算Fib（2）和Fib（1）。 计算Fib（2）计算Fib（1）和Fib（0）。 现在我们回去再次计算Fib（2）。 然后我们回去再次计算Fib（3）。 大量的重新计算。
假设我们caching了计算结果。 然后第二次请求计算，我们只是返回caching的结果。 现在是高阶技巧。 我想把这个“caching一个函数的结果”的概念表示为一个函数，并返回一个函数，这个函数具有这个好的属性。 我将它作为扩展方法写在函数上：
static Func<A, R> Memoize(this Func<A, R> f) { // Return a function which is f with caching. var dictionary = new Dictionary<A, R>(); return (A a)=> { R r; if(!dictionary.TryGetValue(a, out r)) { // cache miss r = f(a); dictionary.Add(a, r); } return r; }; }
现在我们在Fib上做一些小改动：
Func<long, long> Fib = null; Fib = (long n) => { if (n < 2) return 1; return Fib(n-1) + Fib(n-2); };
好的，我们有我们的非memoizedfunction。 现在，魔法：
Fib = Fib.Memoize();
和繁荣，当我们称之为Fib（5），现在我们做一个字典查找。 5不在字典中，所以我们称之为原始函数。 这就是调用Fib（4），它做了另一个字典查找和错过。 这就叫做Fib（3）等等。 当我们再次调用Fib（2）和Fib（3）时，结果已经在字典中，所以我们不重新计算它们。
编写一个双参数版本：
static Func<A1, A2, R> Memoize(this Func<A1, A2, R>) { ... }
不是很难，只是作为一个练习。 如果你这样做，那么你可以把你原来的漂亮的recursion逻辑，做一个简单的重写成lambda，并说：
progress = progress.Memoize();
突然你的performance会增加，不会损失原有algorithm的可读性。
虽然dynamic规划无疑是解决这类问题的正确方法，但是这个特定的实例显示出可被利用的规律性。
你可以看到这个问题，安排了一些“正确的”和“下”，不要多次计算相同的安排。
例如，大小2问题的解决scheme（在问题中的图像中报告）可以这样看：
→→↓↓ →↓→↓ →↓↓→ ↓→→↓ ↓→↓→ ↓↓→→
因此，对于n边的任何网格，您可以通过组合方法find解决scheme：
from math import factorial n = 20 print factorial(2*n)/(factorial(n)*factorial(n))
2N！ 是20→+ 20↓的排列次数，而两个n！ 说明可以安排→和↓的相同方式。
顺便说一句，你可以通过认识到2×3将具有相同数量的path作为3×2来提高你的性能。 您的记忆function似乎只占一个string，正好是列x行。 但是你可以在记忆中join2×3和3×2的关键path。
所以当你记住4×2等，它会自动填充2×4与相同数量的path。 这会减less你的时间，因为你已经计算过所有的path，所以为什么又这样呢？
尽pipedynamic规划看起来像是解决问题的一种有吸引力的方式（并且使其成为一个有趣的编码挑战），但对数据结构的一些创造性思考有助于立即给出答案。
[其余的部分主要是解释为什么Tim Goodman的答案是最好的，因为某些价值是“最好的”]
如果我们有一个nXm网格，我们可以将每个有效的转angular路线表示为一个n + m位串，使用0或1表示“down”。 稍微思考一下，路线的确切数量是从N + M个项目中取N个项目的方法的数量，并且这恰好是关于N的标准简单组合M.
（n + m） （n + m-1） …（m + 1）/（n * （n-1）* … 1）。
最快的程序是不需要存储的程序，在存储方式中使用很多，并且（最好）有一个封闭的答案。
实际上，您正在计算使用泰勒级数的闭合公式的加泰罗尼亚数 。
因此，一个计算解决scheme的程序可以计算二项式系数，如果你没有BigInt类，那么很难得到正确的二项式系数。
你可以把计算时间减半，考虑到一旦你减less到一个平方，网格将是对称的。 因此，无论何时在X方向和Y方向上有相等的空间来遍历剩余空间，对于增加的X行程和增加的Y行程，都可以使用相同的计算方法。
这就是说，我在Python中做了这个，并做了大量的caching结果，以避免重新计算。
解决scheme沿着从网格的NW到SE的对angular线reflection。 所以，你应该只是计算网格的右上angular的解决scheme，然后反映他们得到另一半…
我相信一些高中math在这里会有用，这个环节解释了所需的组合公式：
http://mathworld.wolfram.com/Combination.html
现在，用这个来找出通过一个正方形网格的path数量，公式变成2nselectn。 作为一个警告，你将需要使用一个数据types，可以容纳一个相当大的数字
每个人都表示dynamic编程和caching结果。 我有，在某个地方，一个Ruby脚本结束了一个非常大的哈希所有的数据存储。 事实上，和大多数欧拉项目问题一样，这是一个隐藏的math“窍门”，有办法用简单的计算来得到结果。
我的解决scheme是有效的，但很容易理解：
在一个网格上给定路口的路线数量是到其两个邻居的路线数量的总和。
由于只有一条路线通往顶部和左边的每个点，所以很容易迭代剩下的点并填充空白。
对于x或y = 0：grid [x，y] = 1
对于x和y> = 1：grid [x，y] = grid [x-1，y] + grid [x，y-1]
所以遍历所有的正方形后，最终的答案被包含在网格中[20,20]。
这个问题比许多人所做的要简单得多。 path必须是20个“权利”和20个“起落”的序列。 不同序列的数量是你可以从可能的40个中select20个位置（比如说）“权利”的方法的数量。
