python中的递归公式用于递归sigma如何？

Question

我最近问了这个问题并得到了第一个答案.我想把它放到python代码中.这就是我所拥有的,但我一直得到0作为答案.

def f(n, k, s):
    ans = 0
    for j in range(1, min({k,s}) + 1):
        print j
        if (n == 1):
            if (k >= s):
                ans = ans + 1
            elif (k < s):
                ans = ans + 0
            elif (s > n):
                ans = ans + 0
        elif (n*k < s):
            ans = ans + 0
        else:
            ans = ans + f(n-1,j,s-j)
    return ans

print f(10, 12, 70)

我的代码出了什么问题？我需要改变什么？我不知道出了什么问题.请帮忙.谢谢!

Answer 1

你的代码太复杂了.您可以在数学交换中写出几乎一对一的答案:

def f(n, k, s):
    if n == 1:
        return int(k >= s)
        # or: 1 if k >=s else 0 
    return sum(f(n-1, j, s-j) for j in range(1, min(k, s)+1))
    # to make it faster:
    #return sum(f(n-1, j, s-j) for j in range(1, min(k, s)+1) if n*k >= s)

您的代码中的问题是您将基本案例检查放在循环中,当它应该在外面时:

def f(n, k, s):
    ans = 0
    if n == 1:
        return int(k >= s)

    for j in range(1, min({k,s}) + 1):
        print j
        if n*k >= s:
            ans += f(n-1,j,s-j)
    return ans

通过这两种实现,我获得了12660 f(10, 12, 70).