python - 如何将递归应用于此代码，以求总和为“N”的方式数量？

Question

给定一个整数列表和一个目标整数 N，我想找出可以将列表中的整数相加得到 N 的方法数。允许重复。这是代码：

def countWays(arr, m, N): 

    count = [0 for i in range(N + 1)] 

    # base case 
    count[0] = 1

    # Count ways for all values up  
    # to 'N' and store the result 
    # m=len(arr)
    for i in range(1, N + 1): 
        for j in range(m): 

            # if i >= arr[j] then 
            # accumulate count for value 'i' as 
            # ways to form value 'i-arr[j]' 
            if (i >= arr[j]): 
                count[i] += count[i - arr[j]] 

    # required number of ways  
    return count[N] 

（来自 Geeksforgeeks）

关于如何使用递归和记忆来做到这一点的任何想法？

标签： pythonpython-3.xmath

Answer 1

您要解决的问题与给定面额列表的金额更改方法的数量相同。在您的情况下，金额类似于目标数字 N，面额类似于整数列表。这是递归代码。链接是https://www.geeksforgeeks.org/coin-change-dp-7/

# Returns the count of ways we can sum 
# arr[0...m-1] coins to get sum N 
def count(arr, m, N ): 

    # If N is 0 then there is 1 
    # solution (do not include any coin) 
    if (N == 0): 
        return 1

    # If N is less than 0 then no 
    # solution exists 
    if (N < 0): 
        return 0; 

    # If there are no coins and N 
    # is greater than 0, then no 
    # solution exist 
    if (m <=0 and N >= 1): 
        return 0

    # count is sum of solutions (i) 
    # including arr[m-1] (ii) excluding arr[m-1] 
    return count( arr, m - 1, N ) + count( arr, m, N-arr[m-1] );