改进Ruby函数的性能排列

Question

我试图解决一个10秒超时限制的问题(如果函数运行时间超过10秒，代码被认为是'不正确')。问题是给定一个整数(n)，数字1和2有多少种可能的组合，且和为n?

例:n = 3,组合包括(1 1 1)[1,2](2,1)

我的代码是"正确的"，但运行太慢的编译器，被标记为不正确。我如何使我的代码更高效，为什么它"慢"?另外，应该注意的是，n永远不会超过1000。

require 'benchmark'
def stairs(n)
    possible_combos = []
    ((n/2)..n).each do |i|
        [1,2].repeated_permutation(i) do |combo|
            if combo.inject {|sum, num| sum + num } == n 
                possible_combos << combo 
            end
        end
    end
    puts possible_combos.uniq.length
end
puts Benchmark.measure {stairs(10)}
#=> 0.000000   0.000000   0.000000 (  0.003864)
puts Benchmark.measure {stairs(20)}
#=> 5.720000   0.040000   5.760000 (  5.762111)

Answer 1

存在一些低效之处。最明显的一个是你建立了所有排列的总集合，然后对其进行修剪。在那之后，你也只能取唯一的元素加上另一个(n)运算。相反，我会尝试在第一次构建正确的输出。也许可以利用你知道这个数字是偶数还是奇数的事实。你也知道任意两个1都可以压在一起得到2。你能想出什么巧妙的办法吗?另外，你不需要为每个块中的每个n重新计算。您应该能够缓存结果并重用它们