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

考察的知识点：动态规划；

解答方法分析：

1. 定义一个二维数组dp，dp[i][j]表示在前i个元素中是否存在一个子集，它们的和恰好为j。初始时，dp[0][0]为true。
2. 逐个考虑每个元素weights[i]，对于第i个元素，有两种情况：当weights[i]大于当前的目标值j时，dp[i][j]的值与dp[i-1][j]相同，表示前i-1个元素已经可以组成j的和，第i个元素不用考虑，所以dp[i][j] = dp[i-1][j]。当weights[i]小于等于当前的目标值j时，dp[i][j]的值等于dp[i-1][j]或dp[i-1][j-weights[i]]，即dp[i][j] = dp[i-1][j] || dp[i-1][j-weights[i]]。
3. 如果dp[n-1][target]为true，表示在前n个元素中存在一个子集，其和为target，即列表可以被分割成两个和相等的子集，返回true；否则返回false。

所用编程语言：C++；

完整编程代码：↓

class Solution {
  public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param weights int整型vector
     * @return bool布尔型
     */
    bool canPartition(vector<int>& weights) {
        int n = weights.size();
        int sum = 0;
        for (int i = 0; i < n; i++) {
            sum += weights[i];
        }
        if (sum % 2 != 0) {
            return false;
        }
        int target = sum / 2;
        vector<vector<bool>> dp(n, vector<bool>(target + 1, false));
        for (int i = 0; i < n; i++) {
            dp[i][0] = true;
        }
        for (int i = 1; i <= target; i++) {
            if (weights[0] == i) {
                dp[0][i] = true;
            }
        }
        for (int i = 1; i < n; i++) {
            for (int j = 1; j <= target; j++) {
                if (weights[i] > j) {
                    dp[i][j] = dp[i - 1][j];
                } else {
                    dp[i][j] = dp[i - 1][j] || dp[i - 1][j - weights[i]];
                }
            }
        }
        return dp[n - 1][target];
    }
};