题解 | #牛牛的目标特征数#

思路

凑硬币原题。考点是完全背包，即每种物品可以选无限个。

定义 f[j] 表示前 个物品中选择物品总面值为 时的总硬币数。

定义状态转移方程：f[j] = max(f[j], f[j - features[i]] + 1)。即考虑从之前的状态中比较面值为 和面值为 硬币的数量。如果选择前者，则表示不选择当前面值的硬币，否则选择当前面值的硬币，然后加 。

时间复杂度为 ，空间复杂度为 ，其中 为物品数量， 为背包容量。

参考代码

import java.util.*;


public class Solution {
    final int INF = 0x3f3f3f3f;
    
    public int minAnimalCount (int[] features, int target) {
        int[] f = new int[target + 1];
        int n = features.length;
        
        Arrays.fill(f, INF);
        f[0] = 0;
        for (int i = 0; i < features.length; i++) {
            for (int j = features[i]; j <= target; j++) {
                f[j] = Math.min(f[j], f[j - features[i]] + 1);
            }
        }

        return f[target] == INF ? -1 : f[target];
    }
}