我正在运行Project Euler编码档案，遇到了问题115，上面写着：
"注：这是问题114的一个更难的版本。
长度为n个单位的行具有最小长度的红色块放置在其上的m个单位，使得任意两个红色块(允许有不同的长度(由至少一个黑色分隔广场
让填充计数函数F(m，n(表示方式的数量可以填充一行。
例如，F(3,29(=673135和F(3,30(=1089155。
也就是说，对于m＝3，可以看出n＝30是最小值填充计数函数首先超过一百万。
同样，对于m=10，可以验证F(10，56(=880711和F(10，57(=1148904，因此n=57是填充计数函数首先超过一百万。
对于m=50，找到填充计数为的n的最小值函数首次超过一百万">
对我来说，使用蛮力方法(使用三个嵌套的for循环和中间的大量while循环，跨越大约50行代码(来解决这个问题是可以管理的。相比之下，我发现了一小段利用动态编程的代码：
m, n = 50, 168
ways = [1]*(m) + [0]*(n-m+1)
for k in range(m, n+1):
ways[k] = ways[k-1] + sum(ways[:k-m]) + 1
ways[n]
现在我觉得这很优雅！我理解代码的技术部分，但我不明白这段代码是如何解决问题的。希望在这里获得解释性帮助。
设ways[k]为长度为k的行所需的可能性数。对于k = 0到k = m - 1，我们不能放置任何红色块，所以只有一种可能性：不放置任何东西。因此，我们用1初始化ways的第一个m值。对于k = m以后，我们可以用第k个单元做三件事。首先我们可以将其设置为黑色。这样做的总方法数与分配k - 1的方法数相同，因为除了为k - 1所做的选择之外，我们没有对位置做出任何选择。我们可以做的第二件事是为整个k长度分配一个巨大的红色块。只有一种方法可以做到这一点。第三种选择是指定一个不占用整行的红色块。假设这个新块开始之前的黑色正方形(必须总是有一个，因为我们已经讨论了块跨越整个区域的情况(具有索引i。我们知道i受i + m < k的约束，因为块的长度必须至少为m，所以减去m，我们得到i < k - m。因此，对于第三种情况，我们希望考虑每个有效的i(从i = 0开始，直到但不包括i = k - m(，并将我们可以在i + 1开始红块的所有可能方式相加，这是由sum(ways[:k-m])计算的。将每个案例相加对应于所执行的递归：ways[k] = ways[k-1] + sum(ways[:k-m]) + 1。对于任何n，答案现在都在ways[n]中。最后要注意的是，该算法的复杂性可以通过更复杂的数据结构进一步提高，以通过更新有效地回答前缀和查询。