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]