[leetcode] problem 1049 – last stone weight ii

We have a collection of rocks, each rock has a positive integer weight.

Each turn, we choose any two rocks and smash them together. Suppose the stones have weights x and y with x <= y. The result of this smash is:

• If x == y, both stones are totally destroyed;
• If x != y, the stone of weight x is totally destroyed, and the stone of weight y has new weight y-x.

At the end, there is at most 1 stone left. Return the smallest possible weight of this stone (the weight is 0 if there are no stones left.)

Example

Note

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

public int (int[] stones) {
    int sum = 0;

    for (int stone : stones)
        sum += stone;
    
    int n = sum / 2;
    int[] dp = new int[n + 1];

    for (int i = 0; i < stones.length; i++) {
        int stone = stones[i];

        for (int j = n; j >= stone; j--)
            dp[j] = Math.max(dp[j], dp[j - stone] + stone);
    }

    return sum - 2 * dp[n];
}