class Solution(object):
def canPartition(self, nums):
"""
:type nums: List[int]
:rtype: bool
"""
# guard phase
# 处理异常情况
sum = 0
for n in nums:
sum+=n
if sum%2==1:
return False
target_num = sum//2
print target_num
dp = [[False]*(target_num+1) for _ in range(len(nums)+1)]
# init
# 使用前 i 个元素组成空集,是 ok 的 TRUE
# dp[i][0] 表示的是上面提示的意思
for i in range(len(nums)+1):
dp[i][0] = True
for i in range(1, len(nums)+1):
for j in range(1, target_num+1):
if j>= nums[i-1]:
dp[i][j] = dp[i-1][j] or dp[i-1][j-nums[i-1]]
else:
dp[i][j] = dp[i-1][j]
return dp[-1][-1]
416. 分割等和子集
©著作权归作者所有,转载或内容合作请联系作者
- 文/潘晓璐 我一进店门，熙熙楼的掌柜王于贵愁眉苦脸地迎上来，“玉大人，你说我怎么就摊上这事。” “怎么了？”我有些...
- 文/花漫 我一把揭开白布。 她就那样静静地躺着，像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上，一...
- 文/苍兰香墨 我猛地睁开眼，长吁一口气：“原来是场噩梦啊……” “哼！你这毒妇竟也来了？” 一声冷哼从身侧响起，我...
推荐阅读更多精彩内容
- 给定一个只包含正整数的非空数组。是否可以将这个数组分割成两个子集，使得两个子集的元素和相等。 京东2018校招求神...
- 武汉华信梦科技有限公司在室内空气治理行业是领航者企业，治理技术遥遥领先，治理后绝不反弹，一直以来是零投诉企业。
- HTML5的localStorage是个好东西，可以把数据存在浏览器本地。不过如果要存储数组和json，那就需要把...
- 2-21【子曰：“人而无信，不知其可也。大车无輗，小车无軏，其何以行之哉？”】 信，在为政中，就不仅是对个人的影响...
