7 language-agnostic dynamic-programming
"假设您想要用4×1和6×1乐高积木的行来构建实体面板.对于结构强度,块之间的空间必须永远不会排列在相邻的行中.例如,显示的是18×3面板下面是不可接受的,因为前两行中的块之间的空格对齐.
有2种方法可以构建10×1面板,2种方法可以构建10×2面板,8种方法可以构建18×3面板,7958种方法可以构建36×5面板.
有多少种方法可以构建64×10面板？答案将适合64位有符号整数.编写程序来计算答案.你的程序应该运行得非常快 - 当然,它不应该超过一分钟,即使在较旧的机器上也是如此.让我们知道您的程序计算的价值,程序计算该值的时间,以及您运行它的机器类型.将程序的源代码作为附件包含在内."
我最近得到了一个编程难题,并且一直绞尽脑汁试图解决它.我用c ++编写了一些代码,我知道这个数字是巨大的...我的程序运行了几个小时才决定停止它,因为即使在慢速计算机上也需要1分钟的运行时间.有没有人看过类似的拼图？已经有几个星期了,我再也不能把它拿出去了,但这真的让我感到烦恼,我无法正确解决它.有关使用算法的任何建议吗？或者也许可以通过"开箱即用"来解决它的方法.我使用的是制作一个程序,构建4x1和6x1块的每个可能的"层",以形成64x1层.结果是大约3300个不同的层.然后我让我的程序运行并将它们堆叠到所有可能的10层高墙中,没有裂缝排列......正如你可以看到这个解决方案需要很长很长时间.因此,在时间限制内,蛮力似乎无法有效地解决这个问题.任何建议/见解将不胜感激.
主要的见解是:在确定第3行中的内容时,您不关心第1行中的内容,第2行中的内容.
因此,让我们调用如何构建64x1层的"行方案".你说有大约3300行场景.那不是那么糟糕.
我们来计算一个函数:
f(s,r)=将行方案编号"s"放入行"r"的方法的数量,并合法地填充"r"之上的所有行.
(我指的是顶部的行"1",底部的行"10")
如果你想避免掠夺者,请立即停止阅读.
现在清楚了(将行数从1编号到10):
f(s,1)= 1
对于"s"的所有值.
此外,这是洞察力的来源,(使用Mathematica -ish表示法)
f(s, r) = Sum[ f(i, r-1) * fits(s, i) , {i, 1, 3328} ]
其中"fits"是一个函数,它接受两个场景数字,如果你可以合法地将这两行叠加在一起,则返回"1",如果不能,则返回"0".这使用了洞察力,因为放置场景的合法方式的数量仅取决于根据"拟合"在其上方放置场景的方式的数量.
现在,拟合可以预先计算并存储在3328 x 3328字节数组中.那只是大约10兆的内存.(如果你喜欢它并将它存储为一个阵列,那就少了)
那么答案显然是正确的
Sum[ f(i, 10) , {i, 1, 3328} ]