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

import java.util.*;


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

本题考察的知识点是动态规化，所用编程语言是java.

我们需要考虑状态转移方程是如何得到的，最好能够自己画一张二维表就能够清晰的明白自己状态转移方程的建立。首先我们需要统计所有奶牛体重的和是否为偶数，如果不是直接返回false，否则新建一个长为weights.length，宽为奶牛体重和的一半+1的布尔数组，我们需要将数组的第一列赋值为true,体重和为0肯定是能够分成两组的。然后进行状态转移

dp[i][j] = dp[i-1][j], j<weights[i-1]时，否则dp[i][j] = dp[i-1][j-weights[i-1]]最后返回数组的最后一个元素