1049. Last Stone Weight II¶
题目信息¶
- 题号:
1049
- 难度:
Medium
- 主题:
石子碰撞、操作顺序选择、最小剩余重量
- 原题:
- 重点:
每次可以任意选择两颗石子碰撞,不要求选择最重者;目标是在所有操作顺序中最小化最终剩余重量
题目重述¶
给定正整数数组 stones。一次操作任意选择两颗重量为 x 和 y 的石子,并设 x <= y。若二者相等,它们同时消失;否则两颗原石子消失,并留下重量为 y - x 的新石子。
不断操作直到至多剩一颗石子。不同的选择顺序可能产生不同结果,请返回最终剩余石子重量能够达到的最小值;若可以全部消除,返回 0。
1 <= stones.length <= 30,1 <= stones[i] <= 100。
自建示例¶
最优顺序使两组总重量尽量接近:
输入:stones = [2,3,4,7]
输出:2
解释:可以先让 7 与 4 碰撞留下 3,再让两个 3 同时消失,最后剩下重量 2;不存在使全部石子消失的操作顺序。
只有一颗石子:
输入:stones = [6]
输出:6
解释:无法执行碰撞操作,最终剩余重量就是 6。