algorithm - 仅使用两个操作将数组转换为排序数组

Question

我在一个在线论坛上发现了这个问题:真的很想知道它是如何解决的:

给定一个正整数数组 A。以最低成本将其转换为排序数组。唯一有效的操作是:
1) cost = 1 递减
2) 从数组中完全删除一个元素，成本=元素的值

这是一个科技公司的面试问题

Answer 1

注意:原来的答案已被替换为我更有信心的答案(我也可以解释)。这两个答案在我的测试用例集上产生了相同的结果。

您可以使用动态规划方法解决此问题。关键的观察是，将数字递减为原始数组中没有的值是没有意义的。 (非正式证明:假设您将数字O1递减为原始序列中不存在的值X，以避免从结果序列中删除数字O2 > X。那么您可以将O1递减为O2，并减少成本O2-X)。

现在解决方案变得容易理解:它是二维的 DP。如果我们将原始序列d的不同元素的元素排序为排序数组s，则d的长度成为DP的第一维； s的长度成为第二个维度。

我们声明dp[d.Length,s.Length]。 dp[i,j]的值是解决子问题d[0 to i]同时将解决方案的最后一个元素保持在s[j]之下的成本。注:此成本包含剔除小于d[i]的s[j]的成本。

第一行dp[0,j]计算为将d[0]修剪为s[j]的成本，如果d[0] < s[j]则为零。下一行dp[i,j]的值计算为dp[i-1, 0 to j] + trim的最小值，其中trim是将d[i]修剪为s[j]的成本，如果需要删除则为d[i]，因为s[j]是大于d[i]。

答案计算为最后一行dp[d.Length-1, 0 to s.Length]中的最小值。

下面是 C# 中的实现:

static int Cost(int[] d) {
    var s = d.Distinct().OrderBy(v => v).ToArray();
    var dp = new int[d.Length,s.Length];
    for (var j = 0 ; j != s.Length ; j++) {
        dp[0, j] = Math.Max(d[0] - s[j], 0);
    }
    for (var i = 1; i != d.Length; i++) {
        for (var j = 0 ; j != s.Length ; j++) {
            dp[i, j] = int.MaxValue;
            var trim = d[i] - s[j];
            if (trim < 0) {
                trim = d[i];
            }
            dp[i, j] = int.MaxValue;
            for (var k = j ; k >= 0 ; k--) {
                dp[i, j] = Math.Min(dp[i, j], dp[i - 1, k] + trim);
            }
        }
    }
    var best = int.MaxValue;
    for (var j = 0 ; j != s.Length ; j++) {
        best = Math.Min(best, dp[d.Length - 1, j]);
    }
    return best;
}

这种直接实现的空间复杂度为O(N^2)。您可以通过观察同时使用最后两行来将其减少为O(N)。