我需要打印出数字N可以表示为1,3,4之和的不同方式。
例如n = 5:
我正在使用动态编程解决方案来查找n可以写为1,3,4之和的可能方式的数量
for i in range(4, n + 1):
DP[i] = DP[i - 1] + DP[i - 3] + DP[i - 4]
return DP[n]
可行,我得到了可以表达N的可能方法的数量,在这种情况下为6,但是我不确定如何打印出所有不同的方法:
任何建议都值得欢迎,谢谢!
此递归生成器将产生实际的组合:
def combis(n):
if n < 0:
return
if n == 0:
yield []
for x in (1, 3, 4):
for combi in combis(n-x):
yield [x] + combi
>>> list(combis(5))
[[1, 1, 1, 1, 1], [1, 1, 3], [1, 3, 1], [1, 4], [3, 1, 1], [4, 1]]
当然,这不是DP,而是简单的未缓存和性能不佳的递归实现。但是它应该为DP解决方案提供指导。
本文收集自互联网,转载请注明来源。
如有侵权,请联系 [email protected] 删除。
我来说两句