心路历程经典动态规划问题做完才发现是一类背包问题建模状态第i个数字当前目标和动作选 or 不选返回值当前状态是否存在满足目标和的解bool注意的点1、递归边界可以只考虑选择第0个数字解法动态规划背包问题和树问题适合递归DPclassSolution:defcanPartition(self,nums:List[int])-bool:total_sumsum(nums)iftotal_sum%21:returnFalse# 奇数和不可能划分targettotal_sum//2nlen(nums)# 思路一回溯遍历找找到大于等于target就剪枝# 思路二dpcachedefdp(i,asum):# 能否在[0,i]范围内找到和为asum的子集ifi0:returnnums[0]asum# 不能不选returndp(i-1,asum-nums[i])ordp(i-1,asum)returndp(n-1,target)转化成数组DPfromtypingimportListclassSolution:defcanPartition(self,nums:List[int])-bool:total_sumsum(nums)iftotal_sum%21:returnFalsetargettotal_sum//2nlen(nums)# dp[i][j] 表示前 i1 个数字能否凑出和为 jdp[[False]*(target1)for_inrange(n)]# 边界只考虑第0个数字ifnums[0]target:dp[0][nums[0]]Trueforiinrange(1,n):forjinrange(target1):# 不选当前数字dp[i][j]dp[i-1][j]# 选当前数字前提是 j nums[i]ifjnums[i]:dp[i][j]dp[i][j]ordp[i-1][j-nums[i]]returndp[n-1][target]
Leetcode 416. 分割等和子集
心路历程经典动态规划问题做完才发现是一类背包问题建模状态第i个数字当前目标和动作选 or 不选返回值当前状态是否存在满足目标和的解bool注意的点1、递归边界可以只考虑选择第0个数字解法动态规划背包问题和树问题适合递归DPclassSolution:defcanPartition(self,nums:List[int])-bool:total_sumsum(nums)iftotal_sum%21:returnFalse# 奇数和不可能划分targettotal_sum//2nlen(nums)# 思路一回溯遍历找找到大于等于target就剪枝# 思路二dpcachedefdp(i,asum):# 能否在[0,i]范围内找到和为asum的子集ifi0:returnnums[0]asum# 不能不选returndp(i-1,asum-nums[i])ordp(i-1,asum)returndp(n-1,target)转化成数组DPfromtypingimportListclassSolution:defcanPartition(self,nums:List[int])-bool:total_sumsum(nums)iftotal_sum%21:returnFalsetargettotal_sum//2nlen(nums)# dp[i][j] 表示前 i1 个数字能否凑出和为 jdp[[False]*(target1)for_inrange(n)]# 边界只考虑第0个数字ifnums[0]target:dp[0][nums[0]]Trueforiinrange(1,n):forjinrange(target1):# 不选当前数字dp[i][j]dp[i-1][j]# 选当前数字前提是 j nums[i]ifjnums[i]:dp[i][j]dp[i][j]ordp[i-1][j-nums[i]]returndp[n-1][target]
