[数据结构与算法]最后一块石头的重量 II java

这道题其实也是01背包问题，废话不多说直接看代码喽。
因为这道题的思路和我上篇发布的其实是一样的，所以在这就一带而过咯。。
上篇详细解答：
https://editor.csdn.net/md/?articleId=120949858

 public int lastStoneWeightII(int[] stones) {
          int n=stones.length;
          int sum=0;
          for(int i=0;i<n;i++){
              sum+=stones[i];
          }
          int weight=sum>>1;
          int []dp=new int [weight+1];
          for(int i=0;i<n;i++){
              for(int j=weight;j>=stones[i];j--){
                  dp[j]=Math.max(dp[j],dp[j-stones[i]]+stones[i]);
              }
          }
          return sum-2*dp[weight];
    }

对于最后的返回值，解释一下，就是求出最大值，对应最有解，是sum-dp[weight]于dp[weight]两者的。