大家好，我是前端西瓜哥。三个月没做算法题了。这次我会做一个难度较低的动态规划问题。给定一个只包含正整数的非空数组nums。请判断这个数组是否可以分成两个子集，使得两个子集的元素之和相等。示例1：输入：nums=[1,5,11,5]输出：true解释：数组可以拆分为[1,5,5]和[11]。示例2：输入：nums=[1,2,3,5]输出：false解释：数组不能拆分为两个元素和相等的子集。题目来源：https://leetcode.cn/problems/partition-equal-subset-sum。对于求解问题的动态规划，其模型需要符合多阶段决策最优解模型，即要推导出最终结果，需要经过多个阶段。例如，在经典的跳楼梯中，如果你想跳到第7步，你需要知道跳到第5和第6步需要走多少步。另一个例子是0-1背包问题。当我们在决定是否放第n件物品时，需要知道上一次决定完成后书包所有可能的重量。这些是阶段。我们让多个选择同时并行发生，生成一个stage，记录状态，以供下一个状态使用。让我们言归正传。题意是问是否可以将数组拆分成两个子数组，并且两个子数组的和相等。其实这就相当于数组元素中是否存在子数组，其和就是原数组的和除以2。此时就变成了经典的0-1背包问题。你需要决定是否输入一个特定的数组元素，直到总和刚好除以2。0-1背包问题是在书包具有最大承重能力的情况下，求一个物体的最大重量。或者升级到二维，求物体的最大值。这个问题属于前者。先看完整的解决方案：functioncanPartition(nums){constsum=nums.reduce((sum,curr)=>sum+curr,0);如果(sum%2===1)返回false；consthalf=sum/2;如果(nums[0]===half)返回true；constdp=newArray(nums.length);for(leti=0;i
