题解 | #训练聪明的牛II#

• 题目考察的知识点 : 动态规划
• 题目解答方法的文字分析：

1. 对于给定的草料重量数组 weights 和总重量 target，我们定义状态 dp[i] 表示达到重量 i 所需的最少草料数。注意：这里的「最少草料数」指的是体积为 i 的背包所需的最少物品数量，而不是价值或重量之和。
2. 第一个情况表示达到重量为 0 不需要任何草料。
3. 第二个情况表示对于任意的重量 i，它可以由重量为 i - w[j] 的状态转移而来，因此其最少草料数应该为 dp[i - w[j]] + 1，其中 j 是满足 i-w[j] >= 0 且 w[j] 是给定的草料重量的下标。
4. 第三个情况表示无法凑出重量 i，则将 dp[i] 置为 -1。
5. 最终返回 dp[target] 即可。

• 本题解析所用的编程语言: Python
• 完整且正确的编程代码

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

        for i in range(1, totalWeight + 1):
            for j in range(n):
                if i - weights[j] >= 0:
                    dp[i] = min(dp[i], dp[i - weights[j]] + 1)
        
        return dp[totalWeight] if dp[totalWeight] != float('inf') else -1