JustSong Archive Link About
Projects
Categories
Others

LeetCode 416 Partition Equal Subset Sum

Tag: LeetCode 动态规划 Posted on 2020-03-11 17:37:20 Edited on 2020-06-07 11:12:27 Views: 147

题目链接

第一种状态定义

dp[i][s]

将题目所给的数字数组分为两部分,左边的部分我们还没确定,右边的部分我们已经确定要放到哪一个子集里,将左边的部分的数字个数记为 i。

其中一个子集里元素的和 s,有了 i 和 s 之后我们就可以算出另一个子集中元素的和。

在这种状态定义下,需要消耗大量的空间,原因就在于 s 的范围为 0 ~ 元素个数*元素的最大可能值

第二种状态定义

仔细分析题目,nums 数组是给定的,我们需要将其分为相等的两个部分,那么分出来的值也是确定的,即 sum(nums)/2

定义状态 dp[j] 表示值 j 能否从 nums 的子集中构建出来(里面存储的是一个布尔值)。

那答案就是 dp[sum(nums)/2]

未经允许,禁止转载,本文源站链接:https://iamazing.cn/