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

知识点：动态规划

思路：

1. 首先计算数组weights的总和sum，使用Arrays.stream方法对数组元素求和。
2. 如果sum除以3的余数不为0，则无法分割成三个相等的子集，直接返回false。
3. 将sum除以3，得到目标子集的和，即sum/3。
4. 初始化变量s为0，用于存储当前累计的和。
5. 获取数组weights的长度n。
6. 创建一个大小为(sum+1) x (sum+1)的布尔数组f，用于记录能否得到和为j、k、s - j - k的三个部分的子集。
7. 初始化f[0][0]为true，表示可以得到和均为0的三个子集（即不选取任何元素）。
8. 使用双重循环，遍历数组weights的每个元素和累计和s。
9. 从sum向下遍历到0，更新f[j][k]的值：如果s - j - k大于sum，表示s - j - k的值超过了目标子集和，此时f[j][k]为false。如果j大于等于weights[i]，则能否得到和为j的子集取决于能否得到和为j - weights[i]的子集，即f[j][k]取决于f[j - weights[i]][k]。如果k大于等于weights[i]，则能否得到和为k的子集取决于能否得到和为k - weights[i]的子集，即f[j][k]取决于f[j][k - weights[i]]。
10. 循环结束后，f[sum][sum]即为是否能得到和均为sum的三个子集。
11. 返回f[sum][sum]作为结果。

编程语言：java

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param weights int整型一维数组
     * @return bool布尔型
     */
    public boolean canPartitionII(int[] weights) {
        int sum = Arrays.stream(weights).sum();
        if (sum % 3 != 0) return false;
        sum /= 3;
        int s = 0;
        int n = weights.length;
        boolean[][] f = new boolean[sum + 1][sum + 1];
        // f[i][j][k] 前i个数 能否组成j, k, s - j - k 三个部分
        f[0][0] = true;

        for (int i = 0; i < n; i++) {
            s += weights[i];
            for (int j = sum; j >= 0; j--) {
                for (int k = sum; k >= 0; k--) {
                    if (s - j - k > sum) f[j][k] = false;
                    if (j >= weights[i]) f[j][k] = f[j][k] || f[j - weights[i]][k];
                    if (k >= weights[i]) f[j][k] = f[j][k] || f[j][k - weights[i]];
                }
            }
        }
        return f[sum][sum];
    }
}