<p>我会附上我所有的。和你的一样,唉,时间基本上是<code>O(n**3)</code>。但至少它避免了递归(等等),所以当你接近一百万时不会爆炸;-)注意,这返回找到的最佳向量,而不是计数;例如</p>
<pre><code>>>> solve(23)
[6, 0, 11, 0, 1, 0, 0, 10, 0, 5, 0, 9, 0, 3, 0, 0, 8, 0, 4, 0, 7, 0, 2]
</code></pre>
<p>所以它也显示了选择1位的顺序。获取计数的最简单方法是将结果传递给<code>max()</code>。在</p>
^{pr2}$
<p>或者将函数更改为返回<code>maxsofar</code>,而不是<code>best</code>。在</p>
<p>如果你想计算一百万的数字,你需要的是完全不同的东西。你甚至负担不起二次方时间(更不用说这种方法的立方时间了)。不太可能从更华丽的数据结构中得到如此巨大的改进,我希望它需要对问题的数学有更深入的了解。在</p>
<pre><code>def solve(n):
maxsofar, best = 1, [1] + [0] * (n-1)
# by symmetry, no use trying starting points in last half
# (would be a mirror image).
for i in xrange((n + 1)//2):
v = [0] * n
v[i] = count = 1
# d21[i] = distance to closest 1 from index i
d21 = range(i, 0, -1) + range(n-i)
while 1:
d, j = max((d, j) for j, d in enumerate(d21))
if d >= 2:
count += 1
v[j] = count
d21[j] = 0
k = 1
while j-k >= 0 and d21[j-k] > k:
d21[j-k] = k
k += 1
k = 1
while j+k < n and d21[j+k] > k:
d21[j+k] = k
k += 1
else:
if count > maxsofar:
maxsofar = count
best = v[:]
break
return best
</code></pre>