q3.py 文件源码

def min_coins_count_3(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 _ in range(n)]

        for i in range(1, aim + 1):
            dp[0][i] = max_val
            if arr[0] == i:
                dp[0][i] = 1

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

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