题解 | #农场的奶牛分组#

知识点

动态规划

解题思路

使用二维数组dp保存状态，dp[i][j] 表示前i个奶牛的体重能否凑成j，先初始化dp[i][0] 为true，即前i个奶牛的体重能够凑成 0。然后，使用两层循环进行状态转移，当当前奶牛的体重大于j时，不能选择当前奶牛，继承上一行的状态dp[i-1][j]；否则，可以选择当前奶牛或不选择当前奶牛，继承两种状态中的一个。最后返回dp[n][target] 的结果，即前n个奶牛的体重能否凑成目标体重target。

Java题解

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param weights int整型一维数组
     * @return bool布尔型
     */
    public boolean canPartition (int[] weights) {
        // write code here
        int n = weights.length;
        int sum = 0;
        for (int weight : weights) {
            sum += weight;
        }
        if (sum % 2 != 0) {
            return false;
        }

        int target = sum / 2;

        // dp[i][j] 表示前 i 个奶牛的体重能否凑成 j
        boolean[][] dp = new boolean[n + 1][target + 1];
        for (int i = 0; i <= n; i++) {
            dp[i][0] = true;
        }

        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= target; j++) {
                // 如果当前奶牛的体重大于 j，则不能选择当前奶牛
                if (weights[i - 1] > j) {
                    dp[i][j] = dp[i - 1][j];
                } else {
                    // 否则，可以选择当前奶牛或不选择当前奶牛
                    dp[i][j] = dp[i - 1][j] || dp[i - 1][j - weights[i - 1]];
                }
            }
        }

        return dp[n][target];
    }
}