0

编辑：仍在努力，虽然取得了进展。

def recursion_change(available_coins, tender):
    """
    Returns a tuple containing:
        :an array counting which coins are used to make change, mirroring the input array
        :the number of coins to make tender.

    :coins: List[int]
    :money: int
    :rtype: (List[int], int)
    """
    change_list = [0] * len(available_coins)



    def _helper_recursion_change(change_index, remaining_balance, change_list):
        if remaining_balance == 0:
            return (change_list, sum(change_list))
        elif change_index == -1 or remaining_balance < 0:
            return float('inf')
        else:
            test_a = _helper_recursion_change(change_index-1, remaining_balance, change_list)
            test_b = _helper_recursion_change(_helper_recursion_change(len(available_coins)-1, tender, change_list))

            test_min = min(test_a or test_b)

            if :
                _helper_recursion_change()
            else:
                _helper_recursion_change()
    return 1 + _helper_recursion_change(change_index, remaining_balance-available_coins[change_index], change_list))

print str(recursion_change([1, 5, 10, 25, 50, 100], 72)) # Current Output: 5
# Desired Output: ([2, 0, 2, 0, 1, 0], 5)

快速概述：这个硬币找零算法应该接收可能的找零选项和投标列表。它应该递归地输出一个镜像数组和进行招标所需的硬币数量，我认为最好的方法是使用元组。

例如：

> recursion_change([1, 2, 5, 10, 25], 49)

>> ([0, 2, 0, 2, 1], 5)

工作代码示例：

http://ideone.com/mmtuMr

def recursion_change(coins, money):
    """
    Returns a tuple containing:
        :an array counting which coins are used to make change, mirroring the input array
        :the number of coins to make tender.

    :coins: List[int]
    :money: int
    :rtype: (List[int], int)
    """
    change_list = [0] * len(coins)

    def _helper_recursion_change(i, k, change_list):
        if k == 0: # Base case: money in this (sub)problem matches change precisely
            return 0
        elif i == -1 or k < 0: # Base case: change cannot be made for this subproblem
            return float('inf')
        else: # Otherwise, simplify by recursing:
            # Take the minimum of:
                # the number of coins to make i cents
                # the number of coins to make k-i cents

            return min(_helper_recursion_change(i-1, k, change_list), 1 + _helper_recursion_change(i, k-coins[i], change_list))
    return (_helper_recursion_change(len(coins)-1, money, change_list))

print str(recursion_change([1, 5, 10, 25, 50, 100], 6)) # Current Output: 2

# Desired Output: ([1, 1, 0, 0, 0, 0], 2)

特别是，这一行：

1 + _helper_recursion_change(i, k-coins[i], change_list))

正如程序现在所做的那样，捕获我们需要的硬币数量很容易。我是否必须更改返回值以包含 change_list，以便我可以增加它？在不弄乱递归的情况下最好的方法是什么，因为它目前只返回一个简单的整数。

用 change_list[i] + 1 替换上面列表中的 change_list 会给我 a TypeError: 'int' object is unsubscriptableor change_list[i] += 1 运行失败，因为它是“无效语法”。

4

0 回答 0