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

#include <vector>
class Solution {
  public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param features int整型vector
     * @param target int整型
     * @return int整型
     */
    int minAnimalCount(vector<int>& features, int target) {
        if (target == 0) return 0;
        // 重新存数据
        n = features.size();
        for (int i = 1; i <= n; ++i) {
            a[i] = features[i - 1];
        }
        // 初始化
        for (int i = 1; i <= n; ++i) {
            int j = a[i];
            dp[i][j] = 1;

        }
        // 递推
        for (int i = 1; i <= n; ++i) {
            for (int j = 0; j <= target; ++j) {
                dp[i][j] = min(dp[i][j], dp[i - 1][j]);
                if (j - a[i] >= 0)
                    dp[i][j] = min(dp[i][j], dp[i][j - a[i]] + 1);
            }
        }
        int ans = dp[n][target];
        if (ans >= 1e9)
            return -1;
        else
            return ans;
    }
    int n;
    vector<int> a = vector<int>(15, 0); // 重新存数据
    // dp[i][j] 前 i 个物品构造 j 所需的物品数量的最小值
    // dp[i][j] = min(dp[i][j - a[i]] + 1)
    vector<vector<int> > dp = vector<vector<int> >(15, vector<int>(1e4 + 5, 1e9));
};