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

知识点：动态规划

这道题一开始想要使用DFS，或者BFS，会造成超时或者内存溢出的情况，故需要使用动态规划来解决，我们定义dp[i]为组成 i 需要的元素个数，初始化将已有的元素dp设置为1，同时我们也需要定义dp[0]=0，表示对于目标和为零，我们可以从0开始遍历至目标和，同时，我们遍历更小元素，当我们可以组成j并且可以组成i-j时，我们就可以更新dp[i]为组成i所需要元素的最小值。

Java题解如下

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param weights int整型一维数组 
     * @param totalWeight int整型 
     * @return int整型
     */
    public int minEatTimes (int[] weights, int totalWeight) {
        // write code here
        int n = weights.length;
        int[] dp = new int[totalWeight + 1];
        Arrays.fill(dp, Integer.MAX_VALUE);
        dp[0] = 0;
        for(int weight: weights) {
            if(weight <= totalWeight) dp[weight] = 1;
        }
        for(int i = 0; i <= totalWeight; i++) {
            for(int j = 0; j < i; j++) {
                if(dp[j] != Integer.MAX_VALUE && dp[i - j] != Integer.MAX_VALUE) {
                    dp[i] = Math.min(dp[i], dp[j] + dp[i - j]);
                }
            }
        }
        return dp[totalWeight] == Integer.MAX_VALUE? -1: dp[totalWeight];
    }
}