解题思路

高票答案的思路是开一个target+1长度的数组dp,依次记录能够组合出现的和。其实问题可以转化为生成所有可能的和,并在出现目标和的时候及时停止。我们可以用一个集合rec记录生成的和,一开始rec中只有0;每次遍历nums的一个数字n,并更新rec(每个rec记录的和加上新的数字n,并添加进rec中)。
这种从无到有构建的过程类似于递归解法转化为递推解法,根据DP转移方程自底向上构建状态。这里的状态就是所有可能的和
有所感悟,DP是一种强大的思考方式,但并不一定是目的,经过DP处理过的问题也许可以转化为非DP的处理方法。(当然也可以说本质上还是DP,因为由DP推导所得)
file

代码

class Solution:
    def canPartition(self, nums: List[int]) -> bool:
        s = sum(nums)

        if not nums or len(nums)<2 or s%2:  # 不能被2整除必为False
            return False

        ans = False

        target = s//2

        rec = {0}

        for n in nums:
            for t in tuple(rec):
                rec.add(t+n)
            if target in rec:
                return True

        return False
最后修改日期:2020年10月11日

作者

留言

撰写回覆或留言

发布留言必须填写的电子邮件地址不会公开。