“This is the 12th day of my participation in the Gwen Challenge in November. Check out the details: The Last Gwen Challenge in 2021.”

1049. The weight of the last stone II

Topic describes

We have a bunch of stones, represented by an array of integers called stones. Where stones[I] refers to the weight of the ith stone.

Each round, pick any two stones and smash them together. Suppose the stones weigh x and y, and x <= y. Then the possible results of shredding are as follows:

If x == y, then both stones will be completely shattered; If x! = y, then the stone weighing x will be completely crushed, and the stone weighing Y will have a new weight of Y-x. In the end, there will be no more than one stone left. Returns the minimum possible weight of this stone. If there are no stones left, 0 is returned.

Example 1:

Stones = [2,7,4,1,8,1] Combine 2 and 4 to get 2, so the array becomes [2,7,1,8,1], combine 7 and 8 to get 1, so the array becomes [2,1,1], combine 2 and 1 to get 1, so the array becomes [1,1,1], combine 1 and 1 to get 0, So the array is converted to [1], which is the optimal value.Copy the code

Example 2:

Stones = [31,26,33,21,40Copy the code

Example 3:

Stones = [1,2Copy the code

Method: Dynamic programming

Their thinking

The weight of the last stone, M, can be expressed as sum-neg-neg, where sum is the sum of all integers and neg is the sum of all integers added -, then neg = (sum-m) / 2

To make M as small as possible, neg as large as possible, Max. Math.floor(sum / 2)

Define a two-dimensional Boolean array dp, dp[I][j] indicates whether: select several elements from the first I number of array, and is j

1. Dp [0][0] = true, dp[0][j] = false (j! = 0)

2. i ! = 0 for the ith element num

   If j < num, then dp[I][j] = dp[i-1][j], that is, it is impossible to choose this element, whether the sum of the former i-1 number can be j depends on whether the sum of the former i-1 number can be j

   If j > = num, dp [I] [j] = dp [j] [I – 1] | | dp [I – 1] [j – num], namely the number before I can do it and for j is divided into two cases

   1. beforei-1The number can add up to zerojBefore,iThe number can be in noiThe sum of the numbers is j
   2. beforei-1The number can add up to zeroj-numBefore,iAnd the number can be pickediWhen the sum is j

To optimize the

Since each row of DP is evaluated only with respect to the previous row, instead of using a two-dimensional array, you can use a scrolling array to remove the first dimension of DP

The memory loop should be traversed backwards from the maximum value of j, ensuring that the elements of dp[i-1][] are transferred

code

/ * * *@param {number[]} stones
 * @return {number}* /
var lastStoneWeightII = function(stones) {
    const n = stones.length
    let sum = 0
    stones.forEach(item= > {
        sum += item
    })
    const neg = Math.floor(sum / 2)
    const dp = new Array(neg + 1).fill(false)
    dp[0] = true
    for (let stone of stones) {
        for (let j = neg; j >= stone; j--) {
                dp[j] = dp[j] || dp[j - stone]
        }
    }
    for (let i = neg; i >= 0; i--) {
        if (dp[i]) {
            return sum - 2 * i
        }
    }
};
Copy the code

Algorithm complexity analysis

1. Time complexity: O(n * sum)
2. Space complexity: O(sum)