大家好，我是开车的阿Q，自动驾驶的时代已经到来，没时间解释了，快和阿Q一起上车。作为自动驾驶系统工程师，必须要有最好的C++基础，让我们来一起刷题吧。

题目考察的知识点

本题考察动态规划的解决方法，需要找出最少需要吃几块草料才能达到总重量。

题目解答方法的文字分析

我们可以使用动态规划来解决这个问题。动态规划是一种通过将问题分解为子问题并存储子问题的解来避免重复计算的方法。

具体步骤如下：

  1. 首先，创建一个长度为 totalWeight+1 的一维数组 dp，其中 dp[i] 表示达到重量 i 所需的最少草料数目。
  2. 初始化 dp 数组，将 dp[0]（达到重量为 0）设为 0，其余元素初始化为一个较大的值，例如 INT_MAX，表示初始状态下无法达到该重量。
  3. 对于每块草料的重量 weight，遍历数组 dp，更新 dp[i] 的值：如果 dp[i-weight] 不是初始状态，表示之前已经可以达到重量 i-weight，那么将 dp[i] 更新为 dp[i-weight] + 1。否则，保持 dp[i] 不变，因为当前草料的重量无法达到 i，可能是因为之前的状态无法达到，或者 i-weight 无法达到。
  4. 最终，如果 dp[totalWeight] 的值仍然是初始状态，表示无法准确达到总重量，返回 -1；否则，返回 dp[totalWeight]。

本题解析所用的编程语言

C++

完整且正确的编程代码

#include <vector>
#include <algorithm>
#include <limits.h>

using namespace std;

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param weights int整型vector 草料的重量数组
     * @param totalWeight int整型 需要吃到的总重量
     * @return int整型 最少需要吃几块草料才能达到总重量，无法准确达到则输出-1
     */
    int minEatTimes(vector<int>& weights, int totalWeight) {
        // 创建长度为 totalWeight+1 的一维数组 dp，用于存储达到不同重量所需的最少草料数目
        vector<int> dp(totalWeight + 1, INT_MAX);
        dp[0] = 0; // 初始化达到重量 0 的最少草料数目为 0

        // 遍历每块草料的重量
        for (int weight : weights) {
            // 从 weight 开始遍历 dp 数组，更新 dp[i] 的值
            for (int i = weight; i <= totalWeight; i++) {
                // 如果之前的状态 dp[i-weight] 不是初始状态 INT_MAX，
                // 表示之前已经可以达到重量 i-weight，那么将 dp[i] 更新为 dp[i-weight] + 1，
                // 即加上当前草料，得到达到重量 i 的最少草料数目。
                if (dp[i - weight] != INT_MAX) {
                    dp[i] = min(dp[i], dp[i - weight] + 1);
                }
            }
        }

        // 最终，如果 dp[totalWeight] 的值仍然是初始状态 INT_MAX，
        // 表示无法准确达到总重量，返回 -1；
        // 否则，返回 dp[totalWeight]，即达到总重量所需的最少草料数目。
        return dp[totalWeight] == INT_MAX ? -1 : dp[totalWeight];
    }
};

您的关注、点赞、收藏就是我创作的动力，三连支持阿Q！