956

题目可以看成从数组中找出两个distinct subset使其sum一样且最大

错误想法1

背包找到每个subset sums的数量，然后用总和与这些sums相减判断是否有0出现。很显然不对因为总和里的数完全可以不选

想法2

偷偷看了一眼题解，dp数组用于记录两个柱子中最大的柱子，而i表示两个柱子的差值，即dp[diff] = max(柱子1，柱子2) 有了这个提示那么接下来也不难想到，对于每个新的小柱子i 我们可以选择将其放到任意一边柱子上。那么对于dp[diff]来说，我们可以通过他的含义得到当前diff高柱 = dp[diff], 当前diff矮柱 = 当前diff柱 - diff。 那么如果这个柱子加到高的上面我们得到dp[diff + i] = max(dp[diff + i], dp[diff])， 如果放到矮的上我们发现我们会有两种情况: 一种是两个柱子的差值diff小于i，这样我们不难想象如果放上去我们将会得到dp[i - diff] = max(dp[i - diff], dp[diff] - diff + i);另一种是差值大于等于i 我们可以得到dp[diff - i] = max(dp[diff - i], dp[diff]). 当然因为我们记得是差值我们在判断时必须比较一下dp[i] >= i 小于i 则意味着最高的柱子没有差值高也意味着不成立

题解补充

可以使dp[diff] = sum(两个柱子) 这样我们就可以压缩将放新柱子两种情况进 dp[abs(diff - i)] = max(dp[abs(diff - i)], i + dp[diff] 这样只需最后将结果dp[0]/2就好。