用 N 个数加和 S 的方法数 [英] Number of ways to add up to a sum S with N numbers
问题描述
假设 S = 5 和 N = 3,解决方案看起来像 - <0,0,5> <0,1,4> <0,2,3> <0,3,2> <5,0,0> <2,3,0> <3,2,0> <1,2,2> 等等
Say S = 5 and N = 3 the solutions would look like - <0,0,5> <0,1,4> <0,2,3> <0,3,2> <5,0,0> <2,3,0> <3,2,0> <1,2,2> etc etc.
一般情况下,可以使用N个嵌套循环来解决问题.运行 N 个嵌套循环,在其中检查循环变量是否加起来为 S.
In the general case, N nested loops can be used to solve the problem. Run N nested loop, inside them check if the loop variables add upto S.
如果我们不提前知道 N,我们可以使用递归解决方案.在每一关中,从 0 到 N 运行一个循环,然后再次调用函数本身.当我们达到N的深度时,看看得到的数字加起来是否等于S.
If we do not know N ahead of time, we can use a recursive solution. In each level, run a loop starting from 0 to N, and then call the function itself again. When we reach a depth of N, see if the numbers obtained add up to S.
还有其他动态规划解决方案吗?
Any other dynamic programming solution?
推荐答案
试试这个递归函数:
f(s, n) = 1 if s = 0
= 0 if s != 0 and n = 0
= sum f(s - i, n - 1) over i in [0, s] otherwise
要使用动态编程,您可以在计算 f 后缓存它的值,并在计算之前检查该值是否已存在于缓存中.
To use dynamic programming you can cache the value of f after evaluating it, and check if the value already exists in the cache before evaluating it.
这篇关于用 N 个数加和 S 的方法数的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!