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

• 题目考察的知识点 : 动态规划
• 题目解答方法的文字分析：

1. 可以将奶牛的体重看作物品的体积和价值相等，类比 0-1 背包问题。具体而言，我们可以定义一个三维布尔数组 dp，其中 dp[i][j][k] 表示是否可以从前 i 头奶牛中选取若干头，使得它们分成三组，每组的体重之和分别为 j、k 和 sum/3，其中 sum 是所有奶牛的体重之和
2. dp[i][j][k]=dp[i−1][j][k] or dp[i−1][j−weight[i]][k] or dp[i−1][j][k−weight[i]]
3. 如果不选取第 i 头奶牛，则 dp[i][j][k] 取决于前 i-1 头奶牛是否可以分成体重和为 j、k 和 sum/3 的三组；如果将第 i 头奶牛分到第一组，则 dp[i][j][k] 取决于前 i-1 头奶牛是否可以分成体重和为 j-weight[i]、k 和 sum/3 的三组；如果将第 i 头奶牛分到第二组，则 dp[i][j][k] 取决于前 i-1 头奶牛是否可以分成体重和为 j、k-weight[i] 和 sum/3 的三组。
4. 最终答案即为 dp[n][sum/3][sum/3]，其中 n 是奶牛的数量，sum 是所有奶牛的体重之和。注意到如果 sum 不是 3 的倍数，则无法将奶牛分成三组体重相等的部分，此时直接返回 False。

• 本题解析所用的编程语言: Python
• 完整且正确的编程代码

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param weights int整型一维数组 
# @return bool布尔型
#
class Solution:
    def canPartitionII(self , weights: List[int]) -> bool:
        n, total = len(weights), sum(weights)
        if total % 3 != 0:
            return False
        target = total // 3
        dp = [[[False] * (target + 1) for _ in range(target + 1)] for _ in range(n + 1)]
        for i in range(n + 1):
            dp[i][0][0] = True
        for i in range(1, n + 1):
            for j in range(target + 1):
                for k in range(target + 1):
                    if j >= weights[i-1]:
                        dp[i][j][k] |= dp[i-1][j-weights[i-1]][k]
                    if k >= weights[i-1]:
                        dp[i][j][k] |= dp[i-1][j][k-weights[i-1]]
                    dp[i][j][k] |= dp[i-1][j][k]
        return dp[n][target][target]