为何贪心策略适用于数组合并成回文的最少操作问题？

首先明确问题：我们要通过合并相邻元素（替换为两者之和），用最少的操作把正整数数组变成回文数组。这个双指针贪心的核心逻辑是每次合并两端中数值较小的那一侧的相邻元素，下面就拆解清楚为什么这招能拿到最优解。

核心逻辑拆解 #

双指针分别从数组两端（left和right）出发，对比当前两端的数值：

• 如果两端数值相等：说明这一对已经符合回文要求，直接把两个指针往中间缩，不用操作。
• 如果左端数值更小：把左端当前元素和它右边的元素合并（也就是nums[left+1] += nums[left]），左指针右移一位，操作数加1。
• 如果右端数值更小：把右端当前元素和它左边的元素合并（nums[right-1] += nums[right]），右指针左移一位，操作数加1。

为什么这么做是最优的 #

要证明贪心策略的最优性，关键在于：任何偏离这个策略的操作，都不会得到比它更少的操作数。咱们结合实际场景和逻辑来理解：

因为所有元素都是正整数，合并操作只会让合并后的数值变大。假设当前左端值L小于右端值R：

• 如果这时候不合并左端，反而去合并右端的元素，合并后的右端值会变成R + nums[right-1]，比原来的R更大，和L的差距只会拉得更开。后续左端肯定需要合并更多元素才能追上右端的合并值，操作次数只会增加。
• 反过来合并左端的L和L+1，得到的新左端值会更接近R，甚至可能直接等于R——这样后续需要的操作次数只会减少，不会增加。

举个实际例子：比如数组[1,3,2,4]

• 按贪心操作：左端1 < 右端4，合并1和3得到[4,2,4]，仅1次操作就得到回文数组，直接结束。
• 如果反着来先合并右端4和2得到[1,3,6]，后续还需要两次合并才能变成回文，总共3次操作，比贪心多了2次。

再比如数组[2,1,3]

• 贪心操作：左端2 < 右端3，合并2和1得到[3,3]，1次操作完成。
• 如果反着合并3和1得到[2,4]，还需要再合并一次，总共2次操作，更差。

总结 #

每次合并较小的那一侧，本质是在快速缩小两端的数值差距，避免因合并较大端导致差距进一步扩大，从而保证每一步操作都朝着最少操作数的方向推进，最终得到最优解。

内容的提问来源于stack exchange，提问作者sleekster