方法数加起来的总和S采用N个数字 [英] Number of ways to add up to a sum S with N numbers

问题描述

说S = 5和n = 3的解决方案会是什么样子 - ＆LT; 0,0,5>＆LT; 0,1,4>＆LT; 0,2,3>＆LT; 0,3,2>＆LT ; 5,0,0>＆LT; 2,3,0>＆LT; 3,2,0>＆LT; 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可嵌套的循环，在他们里面检查循环变量添加个秒。

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.

如果我们不知道ň时间​​提前，我们可以使用递归的解决方案。在每个级别上，从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.

这篇关于方法数加起来的总和S采用N个数字的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！