algorithm - 最小成本增加子序列

Question

假设我们有一个包含 N 个整数的数组 A。问题是我们希望最小化一些从位置 1 开始到位置 N 结束的递增子序列（不一定严格递增）的成本。子序列的总成本是子序列中元素之间转换的总成本。在构建子序列时，从位置 j 转换到位置 i 的成本，其中 i >= j 可以在矩阵 COST[i][j] 中找到。保证存在一些递增的子序列，其中我们从位置 1 开始到达位置 N。数组中的值可能非常大。

例如：

N = 5

A = [0,3,2,3,3]

成本=

[[0,INF,INF,INF,INF],

[3,0,INF,INF,INF],

[3,INF,0,INF,INF],

[5,2,2,0,INF],

[6,0,3,1,0]]

最小成本递增子序列是 (A[1], A[2], A[5]) 或 (0,3,3)。

成本为 COST[2][1] + COST[5][2] = 3 + 0 = 3。

到目前为止，我已经能够修改传统的 O(n^2) dp 解决方案，方法是将 dp[i] 初始化为无穷大，将 dp[1] 初始化为 0，然后循环遍历所有先前的值以扩展子序列。在迭代以前的值时，我只是保持最低成本。

现在我想改进这个解决方案并使它成为 o(nlogn)。我知道可以使用数组和二进制搜索来解决常规 LIS 问题，但我无法修改这种方法来解决这个问题。

标签： algorithmsortingdynamic-programmingbinary-search