"""
63分钱  币值有25分 10分 5分 1分  寻找最少的硬币数
"""


class Solution(object):

    def tan_xin(self, coin_kind, change):
        """
        贪心思想，绝大部分币种都生效，但是在处理一种特殊的币种时不生效，
        [1, 5, 10, 21, 25]  63  只需三张21分即可，但是仍会输出6
        :param coin_kind: list[int]
        :param change: int
        :return: int
        """
        coin_kind.sort(reverse=True)
        num = 0
        i = 0
        while i < len(coin_kind):
            # 如果当前所剩金额大于等于当前最大的零钱币种，就用它
            if change >= coin_kind[i]:
                change -= coin_kind[i]
                num += 1
            else:
                i += 1
        return num

    def recursion(self, coin_kind, change):
        """
        递归方法实现，但是这种会极其的耗时间，因为，我们会发现存在大量的重复计算
        怎么解决呢，开一个列表，记录已经寻找过的解，避免重复计算
        :param coin_kind: list[int]
        :param change: int
        :return: int
        """
        min_num = change
        if change in coin_kind:
            # 最小规模，直接返回1
            return 1

        for coin in coin_kind:
            if change >= coin:
                # 问题分解，去求减去coin后的找零最少硬币法，一直递归到change在coin_kind中，
                # 此时很容易直接求得coin的找零最少硬币数为1
                num = 1 + self.recursion(coin_kind, change-coin)
                if num < min_num:
                    # 记录每次递归得到的最小值返回即可
                    min_num = num

        return min_num

    def prune(self, coin_kind, change, coin_memo):
        """
        剪枝，去掉重复计算
        :param coin_kind:
        :param change:
        :param coin_memo:
        :return:
        """
        min_num = change
        if coin_memo[change] > 0:
            # 先查表，如果表中有，直接返回
            return coin_memo[change]

        if change in coin_kind:
            # 最小规模，直接返回1,记录最优解
            coin_memo[change] = 1
            return 1

        for coin in coin_kind:
            if change >= coin:
                num = 1 + self.prune(coin_kind, change-coin, coin_memo)
                if num < min_num:
                    min_num = num
                    # 记录最优解
                    coin_memo[change] = min_num

        return min_num


solution = Solution()
# print(solution.tan_xin([1, 5, 10, 25], 63))
print(solution.prune([1, 5, 10, 25], 63, [0] * 64))  # 0.1毫秒 巨大的提升
# print(solution.recursion([1, 5, 10, 25], 63))  # 大约40秒
# print(solution.tan_xin([1, 5, 10, 21, 25], 63))