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

知识点

动态规划

思路

状态表示: 定义 f[i] 为总和为i的最小个数，

状态转移: 每一次转移是选定当前选哪一个数字，即

时间复杂度为

AC Code (C++)

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