题解 | #训练聪明的牛II#其实和找零钱是一个题

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param weights int整型一维数组 
# @param totalWeight int整型 
# @return int整型
#
class Solution:
    def minEatTimes(self , weights: List[int], totalWeight: int) -> int:
        # write code here
        dp = [float('inf')] * (totalWeight + 1)
        dp[0] = 0

        for i in range(1, totalWeight + 1):
            for w in weights:
                if w <= i:
                    dp[i] = min(dp[i], dp[i - w] + 1)

        return dp[totalWeight] if dp[totalWeight] != float('inf') else -1