验证严格递增数组最小修改贪心策略正确性及相关疑问

结论：该贪心策略不正确，存在反例 #

反例说明 #

考虑数组 [4, 3, 5]：
按照给定的贪心策略执行：

1. 遍历到i=1（元素3），发现3 <= 4，由于i-2=-1（不存在前前元素），不满足修改前一个元素的条件，于是将a[1]改为4+1=5，数组变为[4,5,5]，修改次数+1。
2. 遍历到i=2（元素5），发现5 <=5，检查a[0]+1=5 <5不成立，于是将a[2]改为5+1=6，数组变为[4,5,6]，修改次数累计为2。

但最优解仅需1次修改：将a[0]的4改为2，数组变为[2,3,5]，满足严格递增要求，修改次数远少于贪心策略的结果。

这个反例暴露了贪心策略的核心缺陷：它仅考虑修改当前元素或前一个元素，完全忽略了修改更前面元素的可能性；同时在i=1的场景下，直接默认选择增大当前元素，而没有评估减小前一个元素的成本，导致引入了不必要的额外修改。

如何判断贪心策略的正确性 #

要确认一个贪心策略是否正确，通常需要验证两个关键性质：

• 贪心选择性质：全局最优解可以通过一系列局部最优的选择逐步构建。也就是说，每一步做出的当前最优选择，不会阻碍后续找到全局最优解。
• 最优子结构性质：问题的最优解包含其子问题的最优解。

验证方法通常有两种：

1. 反证法：假设存在一个最优解不包含当前的贪心选择，然后证明可以通过替换该解中的选择为贪心选择，得到另一个同样最优的解，从而说明贪心选择的有效性。
2. 数学归纳法：证明对于所有规模为k的问题，贪心策略能得到最优解，进而推导到规模为k+1的问题也成立。

如果无法证明这两个性质，或者能找到像上面那样的反例（贪心选择导致结果劣于最优解），那么这个贪心策略就是错误的。

何时需改用动态规划 #

当问题不满足贪心选择性质时，就需要考虑动态规划：

• 当局部最优选择会导致后续需要付出更大的代价，或者无法引导到全局最优解时，贪心策略就失效了。
• 当问题具备重叠子问题和最优子结构性质时，动态规划可以通过记录子问题的解来避免重复计算，从而高效地得到全局最优解。

回到这个问题，经典的解法是转化为求最长严格递增子序列（LIS）：最少修改次数 = 数组总长度 - LIS的长度。因为保留最多的无需修改的元素（即LIS），剩下的元素都需要修改。这个解法可以通过动态规划基础实现（时间复杂度O(n²)），或者优化为O(n log n)的效率，比给定的贪心策略更可靠。

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