【分割等和集】python刷题记录

目录

初始做法（超时）

修改递推式

 空间优化

ps:

润到dp，作为暑期时间段的边界的最后一道题，下一个阶段也应该不错！

初始做法（超时）

sum（nums）绝对是偶数

class Solution:
    def canPartition(self, nums: List[int]) -> bool:
        #sum(nums)必须是偶数
        #记忆化搜索
        #dfs(i,j)代表从nums[0]到nums[i]种选一个和j相等的子序列
        def dfs(i:int,j:int)->bool:
            if i<0:
                return j==0
            #因为有两种情况，选还是不选nums[i]，进入下一个状态
            return j>=nums[i] and dfs(i-1,j-nums[i]) or dfs(i-1,j)
        s=sum(nums)
        return s%2==0 and dfs(len(nums)-1,s//2)
        

 

超时了

修改递推式

 

class Solution:
    def canPartition(self, nums: List[int]) -> bool:
        s=sum(nums)
        if s%2:
            return False
        s//=2
        n=len(nums)
        #初始化
        f=[[False]*(s+1) for _ in range(n+1)]
        f[0][0]=True
        for i,x in enumerate(nums):
            for j in range(s+1):
               f[i+1][j]=j>=x and f[i][j-x] or f[i][j]
        return f[n][s]
        

 空间优化

class Solution:
    def canPartition(self, nums: List[int]) -> bool:
        s=sum(nums)
        if s%2:
            return False
        s//=2
        n=len(nums)
        #初始化
        f=[True]+[False]*s
        s2=0
        for i,x in enumerate(nums):
            s2=min(s2+x,s)
            for j in range(s2,x-1,-1):
               f[j]=f[j] or f[j-x]
        return f[s]
        

 

ps:

灵神也有个题单？？！！

. - 力扣（LeetCode）

原文地址：https://blog.csdn.net/m0_73629042/article/details/140587195

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！