寻找更新动态编程数组的最佳方法

Question

假设有 n 个人排成一排，每个人都有自己独特的价值（从 1 到 n），我们尝试这样对他们进行排序：

repeat
    swapped = false
    for i from 1 to n do:
        if a[i] > a[i+1] then
            add a friendship between a[i] and a[i+1]
            swap(a[i], a[i+1])
            swapped = true
        end if
    end for
until not swapped

如你所见，每一次交换，他们之间都会产生友谊，对于一个人来说，如果他没有与另一个人交换，他们之间就不会有任何友谊，问题是手术完成后一个输入，最多有多少人不是好友？！ 输入示例：

3
3 1 2

输出示例：

2

我尝试使用以下代码解决这个问题：

n = int(input())
permutation = list(map(int, input().split()))
dp = [[] for _ in range(n)]
max_length = 0
for i in range(n):
    dp[i].append(i)
    for j in range(i):
        if permutation[j] < permutation[i]:
            addable = True
            for k in dp[j]:
                if (permutation[k] > permutation[i] and k < i) or (permutation[k] < permutation[i] and k > i):
                    addable = False
                    break
            if addable and len(dp[j]) + 1 > len(dp[i]):
                dp[i] = dp[j].copy()
                dp[i].append(i)
    if len(dp[i]) > max_length:
        max_length = len(dp[i])

print(max_length)

这对于所有输入都非常有效，并且在我检查时为我们提供了正确的答案，但它的时间复杂度为 O(n^3)，这对于大输入来说完全不是很好。 有没有办法优化这段代码？或者至少还有另一种解决方案和方法？！ 此代码假设每次交换时，具有 n 个顶点的完整图中的一条边都会被删除，并且考虑到这一点，当且仅当高于另一个的索引具有更高的值时，两个排列索引之间才会存在边.

Answer 1

为了优化代码，您可以使用基于动态规划的更高效的算法，时间复杂度为 O(n^2)。方法如下：

n = int(input())
permutation = list(map(int, input().split()))
# Initialize an array to store the length of the longest increasing subsequence ending at each
index dp = [1] * n
# Iterate over the permutation
 for i in range(1, n):
for j in range(i):
    if permutation[j] < permutation[i]:
        dp[i] = max(dp[i], dp[j] + 1)

 # The maximum length of the longest increasing subsequence is the answer
 max_length = max(dp)
print(n - max_length)

此代码计算排列的最长递增子序列（LIS）的长度。非好友人数等于总人数 (n) 与 LIS 长度之差。这种方法避免了不必要的检查，并且具有更好的时间复杂度。