LeetCode 416 Partition Equal Subset Sum
第一种状态定义
dp[i][s]
将题目所给的数字数组分为两部分,左边的部分我们还没确定,右边的部分我们已经确定要放到哪一个子集里,将左边的部分的数字个数记为 i。
其中一个子集里元素的和 s,有了 i 和 s 之后我们就可以算出另一个子集中元素的和。
在这种状态定义下,需要消耗大量的空间,原因就在于 s 的范围为 0 ~ 元素个数*元素的最大可能值
。
第二种状态定义
仔细分析题目,nums 数组是给定的,我们需要将其分为相等的两个部分,那么分出来的值也是确定的,即 sum(nums)/2
。
定义状态 dp[j] 表示值 j 能否从 nums 的子集中构建出来(里面存储的是一个布尔值)。
那答案就是 dp[sum(nums)/2]
。