ruby - 给定n，在ruby中如何求出n为1、3、4之和的不同写法的个数？

Question

问题:给定n，找出将n写成1、3、4之和的不同方式的数目示例:对于 n=5，答案是 6

 5=1+1+1+1+1
 5=1+1+3
 5=1+3+1
 5=3+1+1
 5=1+4
 5=4+1

我试过排列法，但是效率很低，有没有更高效的方法呢？

Answer 1

使用带有查找表的动态编程(使用散列实现，因为它使代码更简单):

nums=[1,3,4]
n=5

table={0=>1}
1.upto(n) { |i|
  table[i] = nums.map { |num| table[i-num].to_i }.reduce(:+)
}
table[n]
# => 6

注意:仅检查其他答案之一，我的 n=500 是瞬时的。