给定一个只包含正整数的数组 nums ,请问能否把这个数组取出若干个数使得取出的数之和和剩下的数之和相同。
数据范围: , 数组中的元素满足
class Solution: def partition(self , nums: List[int]) -> bool: '''找重叠子问题''' '''不能只靠脑子想''' target = sum(nums) if target % 2 != 0: return False dp = [[0 for line in range(target//2 + 1)] for row in range(len(nums))] for i in range (1,target//2 + 1): if i < nums[0] : dp[0][i] = dp[0][i-1] else : dp[0][i] = nums[0] for i in range(1,len(nums)): for j in range(1, target//2 + 1): if j < nums[i] : dp[i][j] = dp[i-1][j] else: dp[i][j] = max(dp[i-1][j], nums[i] + dp[i-1][j-nums[i]]) if dp[len(nums)-1][target//2] == target//2: return True else : return False 但是会超时 ,没有做优化。