q3.py 文件源码

def min_coins_count_2(cls, arr, aim):
        if not arr or aim < 0 or len(arr) == 0:
            return -1

        n = len(arr)
        max_val = sys.maxsize
        dp = [0 for _ in range(aim + 1)]
        for i in range(1, aim + 1):
            dp[i] = max_val
            if arr[0] <= i and dp[i - arr[0]] != max_val:
                dp[i] = dp[i - arr[0]] + 1

        for i in range(1, n):
            for j in range(1, aim + 1):
                left = max_val
                if arr[i] <= j and dp[j - arr[i]] != max_val:
                    left = dp[j - arr[i]] + 1
                dp[j] = min([left, dp[j]])

        return dp[aim] if dp[aim] != max_val else -1