我们有一个实数序列。所有数字都是唯一的。我们希望通过更改其中一些值来获得一个升序序列。我们可以更改任意数字。如何找到最佳算法来确定进行此序列所需的最少更改次数？ 我们可以使用贪心或动态规划方法。
最佳答案
首先找到最长的递增子序列 http://en.wikipedia.org/wiki/Longest_increasing_subsequence
然后改变所有不属于这个子序列的数字以符合规则
(证明:如果我们改变较少的数字并获得升序，那么没有改变的数字最初形成递增子序列，长度超过“最长”)
关于algorithm - 这是什么贪婪或动态编程方法？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/26886734/