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

知识点

动态规划

思路

首先我们定义f[i][j][k]为前i个数，能否组成j, k, s - j - k 三个部分。

其中s是前i个数的前缀和。

这样我们根据当前的数w分在哪一个部分，可以由f[i-1][j-w][k]、f[i-1][j][k-w]、f[i-1][j][k]三部分传递过来。

因此假设假设总和为m，时间复杂度为 $O(nm^2)$

其中空间可以优化掉第一维。空间复杂度为 $O(m^2)$

n是200，每个数最大为100，因此总和 $m \leq 7e^3$ ，空间开 $O(m^2)$ 级别也在 $5e^7$ 左右，由于vector<bool>的每一位是1个bit，所以空间是正常的八分之一，空间不会超过6MB

但是考虑计算时间约在 $1e^{10}$ 妥妥超时，但是没想到更好的办法。但是肯定比回溯的时间复杂度要低。

AC Code (C++) 空间二维优化版本

#include <numeric>
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param weights int整型vector 
     * @return bool布尔型
     */
    bool canPartitionII(vector<int>& weights) {
        int sum = accumulate(weights.begin(), weights.end(), 0);
        if (sum % 3) return false;
        sum /= 3;
        int s = 0;
        int n = weights.size();
        vector<vector<bool>> f(sum + 1, vector<bool>(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] or f[j-weights[i]][k]);
                    if (k >= weights[i]) f[j][k] = (f[j][k] or f[j][k-weights[i]]);
                }
            }
        }
        return f[sum][sum];
    }
};