same as leetcode 416, but this one caculate the difference.
time: O(n*m)
space: O(n*m)
classSolution {publicintlastStoneWeightII(int[] stones) {int sum =0;for (int num : stones) { // add them all sum += num; }int n =stones.length;int m = sum/2; // become 01 backpack problems, target is sum/2boolean dp[][] =newboolean[n+1][m+1];int min =Integer.MAX_VALUE; dp[0][0] =true;for (int i =1; i <= n; i++) {for (int j =0; j <= m; j++) {if (j >= stones[i-1]) { dp[i][j] = dp[i-1][j] || dp[i-1][j - stones[i-1]]; } else { dp[i][j] = dp[i-1][j]; }if (dp[i][j]) { // if can fit to sum/2 pack, caculate the diff, the current weight size is jint diff =Math.abs(sum - j*2); min =Math.min(min, diff); } } }return min; }
classSolution {publicintlastStoneWeightII(int[] stones) {int sum =0;for (int num : stones) { // add them all sum += num; }int n =stones.length;int m = sum/2; // become 01 backpack problems, target is sum/2int dp[][] =newint[n+1][m+1]; dp[0][0] =0;for (int i =1; i <= n; i++) {for (int j =0; j <= m; j++) {if (j >= stones[i-1]) { dp[i][j] =Math.max( dp[i-1][j], dp[i-1][j - stones[i-1]] + stones[i-1] ); } else { dp[i][j] = dp[i-1][j]; } } }return sum -2*dp[n][m]; // at last, dp[n][m] fit to sum/2's result, so *2 }}