588. Partition Equal Subset Sum

本题可以转化为求一个subset的和是总和的一半。(当然了如果总和是奇数直接return false)

一开始用DFS和一个全局boolean 来算,只要累加到一个sum是所要的值就赋值全局flag,然后最后查看这个变量。结果数字一多就超时了,只能回归DP的怀抱。所以递归公式就尤其重要.

boolean[] dp = new boolean[target+1];
 dp[0] = true;
 
 for(int i=0; i<nums.length; i++){
 for(int j=target; j>=nums[i]; j — ){
 dp[j] |= dp[j — nums[i]];
 }
 }
 return dp[target];

这里注意两点,

  1. 内层的循环是动态的范围,j从当前数字和target之间,如果j减去本身即nums[i]的值的那个dp值就可以赋给dp[j]。说白了就是dp[j — nums[i]]是true那dp[j]就是true, 如果我已经是true了那就不要烦我。因为我们正看的就是nums[i],相当于sum里去掉它。
  2. 由于dp[j]取决于它前面的dp[j-num[i]]来决定,所以内层循环一定要反方向的,这样才能保证dp[j]计算的时候取的是上一次循环的dp[j-num[i]]的值,如果循环顺序反过来就会因为用了刚更新过的值而出错。
  3. 我转念一想,上一条里,如果倒叙是因为依靠之前的元素,即用减法来的,那我该换用加法,是不是可以正着写循环了?即如下的代码: for(int i=0; i<nums.length; i++){
     for(int j=0; j<=target; j++){
     if(j+nums[i]<=target){
     dp[j+nums[i]] |= dp[j];
     } } } 看上去很对呢,而且也考虑了不要越界等。

还是不对,为什么呢,因为正着循环会较为分散的更新本次的数据,比如j=0的时候,更新的是本次的所有j+num[i]的dp值,并不是线性的更新,这就为后面埋上了隐患,还是会影响某个数字拿到了本次已更新的dp值。而反观倒序地循环,就可以保证dp值是线性更新的,因为就是j- -嘛。所以还是且只能倒序地更新dp

One clap, two clap, three clap, forty?

By clapping more or less, you can signal to us which stories really stand out.