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

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param features int整型一维数组
     * @param target int整型
     * @return int整型
     */
    public int minAnimalCount(int[] features, int target) {
        int[] dp = new int[target +
                           1]; // 创建dp数组，存储组合出每个特征值所需要的最少牛的数量
        Arrays.fill(dp,
                    Integer.MAX_VALUE); // 初始化dp数组，将其值都设为无穷大
        dp[0] = 0; // 目标特征值的位置设置为0

        // 遍历特征值数组
        for (int f : features) {
            // 更新dp数组中可以通过该特征值组合出的特征值的最少牛的数量
            for (int i = f; i <= target; i++) {
                if (dp[i - f] != Integer.MAX_VALUE) { // 如果dp[f-target]不为无穷大
                    dp[i] = Math.min(dp[i], dp[i - f] + 1); // 更新dp[f]
                }
            }
        }

        // 返回组合出目标特征值所需要的最少牛的数量，如果无法组合出目标特征值，返回-1
        return dp[target] == Integer.MAX_VALUE ? -1 : dp[target];
    }
}

本题知识点分析：

1.动态规划

2.数学模拟

3.API函数(Arrays.fill)

本题解题思路分析：

1.先将dp数组都赋值给Integer.MaxValue

2.初始化dp[0]为0

3.取出每一个数字，比如1,2,5 遍历从1-11,2-11,5-11，如果存在dp数组此时的数值不等于maxValue,说明有值被相加，此时更新dp,dp选择当前值和dp[i-f]+1中的较小值，+1其实就是length++，个数+1的意思，选择能够构成11的个数最小的，每次都去取最小，最后dp[target]也就是dp[11]的值，就是能够组合成11的个数最小值

4.如果dp[target]是maxValue,说明没有能够构成11的个数，那么就返回-1即可

本题使用编程语言: Java

如果你觉得本篇文章对您有帮助的话，可以点个赞，支持一下，感谢~