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

考察的知识点：动态规划；

解答方法分析：

1. 创建一个长度为 totalWeight + 1 的数组 dp，并将所有元素初始化为无穷大。
2. 设置初始条件 dp[0] = 0，表示不需要吃货就能达到重量为 0 的状态。
3. 从重量为 1 开始遍历到 totalWeight，对于每个重量 i，遍历待选择的食物重量。如果当前的食物重量 weights[j] 小于等于 i，表示可以选择这个食物，并判断选择这个食物后的状态是否更优（即 dp[i - weights[j]] + 1）。
4. 如果更优，就更新 dp[i] 的值为最小的吃货次数。这样在遍历完所有待选择的食物后，dp[totalWeight] 就表示达到目标重量 totalWeight 的最小吃货次数。
5. 如果 dp[totalWeight] 不等于无穷大，则返回 dp[totalWeight]；否则，返回 -1，表示无法达到目标重量。

所用编程语言：C++；

完整编程代码：↓

class Solution {
  public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param weights int整型vector
     * @param totalWeight int整型
     * @return int整型
     */
    int minEatTimes(vector<int>& weights, int totalWeight) {
        int n = weights.size();
        vector<int> dp(totalWeight + 1, INT_MAX);
        dp[0] = 0;
        for (int i = 1; i <= totalWeight; i++) {
            for (int j = 0; j < n; j++) {
                if (i >= weights[j] && dp[i - weights[j]] != INT_MAX) {
                    dp[i] = min(dp[i], dp[i - weights[j]] + 1);
                }
            }
        }
        return (dp[totalWeight] != INT_MAX) ? dp[totalWeight] : -1;
    }
};