【动态规划】LeetCode 题解：416-分割等和子集

,大家好，我是前端西瓜哥，有三个月没做算法题了，这次就来做一道动态规划中难度较低的题。,给你一个只包含正整数的非空数组 nums。请你判断是否可以将这个数组分割成两个子集，使得两个子集的元素和相等。,示例 1：,示例 2：,题目来源：,https://leetcode.cn/problems/partition-equal-subset-sum。,动态规划，它的模型需要符合 多阶段决策最优解模型，即要推导出最后的结果，它需要经历多个阶段。,比如经典的跳楼梯，假如你要跳到第 7 阶梯的楼梯，你需要先知道跳到第 5 和第 6 阶梯需要走的步数。,还比如 0-1 背包问题，我们在决策是否要放入第 n 个物品，我们需要知道上一个决策完成后，书包的所有可能的重量。,这些都是 阶段。我们让多个选择同时并行发生，产生一个个阶段，并记下状态，给下一个状态使用。,我们回到正题。,题目意思是问能否将数组拆分成两个子数组，这两个子数组的和相等。,其实这就等价于，数组元素中是否存在一个子数组，它的和为原数组的总和除以 2，这时它就变成了经典 0-1 背包问题，你需要决策每个阶段是否放入特定的数组元素，直到刚好为总和除以 2。,先看完整的题解：,这里的要点是构建一个二维布尔值数组 dp，用来保存每个阶段的状态，对于 dp[i][j]，i 表示决策第 i 个元素是否被放入，j 表示子数组总和。,所以 dp[i][j] 的意思就是在决策第 i 个元素的阶段，是否存在一种可能，让总和为 j。,,因为当前阶段需要靠上一个阶段推导，所以我们需要初始化第一阶段的状态：,然后推导下一个阶段时，就遍历上一阶段的值，如果为 true，就基于它决策加入当前元素和不加入当前元素后得到的新的总和，在对应的位置标记为 true，直到和为目标值。,其实还可以做内存优化，将二维数组转换为一维数组，这需要用从后往前遍历数组的技巧。,这里还用二维数组的解法，是因为它还是比较经典的，有普适性，适合用于讲解。一些题目中，甚至能将优化为几个变量，比如跳楼梯。,动态规划，是有一定难度的算法题类型，也是面试大厂时比较常看到的题目，有掌握的必要性。