1049.Last-Stone-Weight-II

1049. Last Stone Weight II

้ข˜็›ฎๅœฐๅ€

https://leetcode.com/problems/last-stone-weight-ii/

้ข˜็›ฎๆ่ฟฐ

You are given an array of integers stones where stones[i] is the weight of the ith stone.

We are playing a game with the stones. On each turn, we choose any two stones 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 destroyed, and
If x != y, the stone of weight x is destroyed, and the stone of weight y has new weight y - x.
At the end of the game, there is at most one stone left.

Return the smallest possible weight of the left stone. If there are no stones left, return 0.

Example 1:
Input: stones = [2,7,4,1,8,1]
Output: 1
Explanation:
We can combine 2 and 4 to get 2, so the array converts to [2,7,1,8,1] then,
we can combine 7 and 8 to get 1, so the array converts to [2,1,1,1] then,
we can combine 2 and 1 to get 1, so the array converts to [1,1,1] then,
we can combine 1 and 1 to get 0, so the array converts to [1], then that's the optimal value.

Example 2:
Input: stones = [31,26,33,21,40]
Output: 5

Example 3:
Input: stones = [1,2]
Output: 1

Constraints:
1 <= stones.length <= 30
1 <= stones[i] <= 100

ไปฃ็ 

Approach #1

่ฟ™้“้ข˜๏ผŒ็›ธๅฝ“ไบŽ็”จๅŠ ๅทๅ’Œๅ‡ๅทๆŠŠ็Ÿณๅคด็š„้‡้‡่ฟž่ตทๆฅ๏ผŒๅนถไฝฟ็ป“ๆžœๆœ€ๅฐใ€‚ๆ‰€ไปฅ้—ฎ้ข˜่ฝฌๆขไธบๆŠŠ็Ÿณๅคดๅˆ†ไธบไธคๆ‹จ๏ผŒไธ€ๆ‹จๆ˜ฏๅธฆๅŠ ๅท๏ผŒไธ€ๆ‹จๆ˜ฏๅธฆๅ‡ๅทใ€‚็›ฎๆ ‡ๆ˜ฏๆฑ‚ๅธฆๅ‡ๅท็š„้‚ฃๆ‹จ็Ÿณๅคด๏ผŒไฝฟๅ…ถๅ’Œ<=sum/2,ๅนถๆŽฅ่ฟ‘ไบŽsum/2๏ผŒ่ฟ™ๅฐฑ็›ธๅฝ“ไบŽ้€‰็Ÿณๅคดๆ”พ่ฟ›่ƒŒๅŒ…๏ผŒไฝฟ่ƒŒๅŒ…ๅฐฝๅฏ่ƒฝ็š„ๆปก๏ผŒ่ƒŒๅŒ…็š„ๅฎน้‡ไธบsum/2๏ผŒๅ„ไธช็Ÿณๅคด็š„ไฝ“็งฏๅ’Œ่ดจ้‡็›ธ็ญ‰้ƒฝไธบstones[i]ใ€‚

Time: O(1) && Space: O(1)

class Solution {
    public int lastStoneWeightII(int[] stones) {
        int n = stones.length;
        int sum = 0;
        for (int i = 0; i < n; i++) {
            sum += stones[i];
        }

        int target = sum / 2;
        int[] dp = new int[target + 1];

        for (int i = 0; i < n; i++) {
           int val = stones[i];
            for (int j = target; j >= val; j--) {
                dp[j] = Math.max(dp[j], dp[j - val] + val);
            }
        }

        return sum - 2 * dp[target];
    }
}

Last updated