q3.py 文件源码

def min_coins_count_4(cls, arr, aim):
        if not arr or len(arr) == 0 or aim < 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 i <= len(arr) - 1:
                if arr[i] == i:
                    dp[i] = 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