java - 动态规划打破一个字符串

Question

目标是计算在用户给定的断点处断弦的成本。因此，让我们假设以下内容:String 的长度 = 10 所以 lengthArray = [1,2,3,4,5,6,7,8,9,10]和 BreakPointArray = [5, 3, 2, 6, 1]。现在我们不必更改用户给出的中断顺序。

我能够找出这个问题的树结构

所以在给定的断点处断开字符串的总成本 = 10+5+5+3+2 = 25但是我无法提出实现部分。以下是我的方法:

我从BreakPoint = 5开始，把lengthArray分成

左长度 = [1,2,3,4,5]

和

右长度 = [6,7,8,9,10]

在 BreakPoint = 3 处，我检查它是否应该在 leftLength 数组下，所以我再次将 leftLength 分成两部分

左长度 1 = [1, 2,3]

和

rightLength1 = [4,5]

在 BreakPoint = 2 处，在 leftLength1 下，所以再次分成两部分

leftLength2 = [1,2] 和

rightLength2 = [3]

现在我在 BreakPoint = 6 时卡住了，因为它在上面的 rightLength 之下。有人可以帮助我如何跟踪我所做的所有分区。我如何返回到第一个 rightLength 数组来计算断点 6 的成本。我正在尝试实现此 Java。

Answer 1

对不起，这是Lua，但是DP算法已经够清楚了

-- input constants
local L = 0
local R = 10
local BreakPoints = {5, 3, 2, 6, 1}

-- fill the arrays
local NearestRight = {}
local NearestLeft = {}
for k = L, R do
   NearestRight[k] = R
   NearestLeft[k] = L
end

-- calculating cost
local cost = 0
for _, BreakPoint in ipairs(BreakPoints) do
   local left = NearestLeft[BreakPoint]
   local right = NearestRight[BreakPoint]
   cost = cost + (right - left)
   for k = left + 1, BreakPoint - 1 do
      NearestRight[k] = BreakPoint
   end
   for k = BreakPoint + 1, right - 1 do
      NearestLeft[k] = BreakPoint
   end
end
print(cost)   -- outputs 25

时间复杂度是O(cost)