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]。
Links: leetcode-416-Partition-Equal-Subset-Sum
未经允许，禁止转载，本文源站链接：https://iamazing.cn/