题解 | #训练聪明的牛II# DP
训练聪明的牛II
https://www.nowcoder.com/practice/79f86360f2894f76b88d33b28a5d09b8
知识点
动态规划
思路
状态表示: 定义 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];
}
};
查看15道真题和解析