동적 프로그래밍 문자열 깨기

목표는 사용자가 지정한 중단 점에서 문자열을 끊는 비용을 계산하는 것입니다. 따라서 다음과 같이 가정하십시오. String의 길이 = 10이므로 lengthArray = [1,2,3,4,5,6,7,8,9,10] 및 BreakPointArray = [5, 3, 2, 6, 1]. 이제는 사용자가 지정한 휴식 시간을 변경할 필요가 없습니다. 나는이 문제동적 프로그래밍 문자열 깨기

enter image description here

의 트리 구조를 알아낼 수 있어요

그래서 = 10 + 5 + 5 + 3 + 2 = 25 주어진 중단 점에서 문자열을 깨는의 총 비용 그러나 나는 구현 부분을 생각해 낼 수 없다. 내가 중단 점 = 5에서 시작 [

leftLength = [1,2,3,4,5]

및

rightLength =으로 6을 lengthArray 분할

: 다음은 내 접근 방식 , 7,8,9,10-] = 3 중단 점에서

, I는 2 부

leftLength1 = [(1)에 I가 leftLength 분할 그래서 다시 leftLength 배열 받고 것을 확인할 1,2,3]

중단 점 = 2에서

rightLength1 = [4,5]

2 개 부분

leftLength2 = [1,2

]로 나누기 때문에 다시 leftLength1 받고 및

rightLength2 = [3] 중단 점 = 6, 그것은 위의 rightLength에서 제공하기 때문에 때

지금 내가 박히. 누군가 내가 할 수있는 모든 파티션을 추적 할 수있는 방법을 도울 수 있습니까? breakPoint 6의 비용을 계산하기 위해 어떻게 첫 번째 rightLength 배열로 돌아갈 수 있습니까?이 자바를 구현하려고합니다.

출처

2014-05-13 daydreamer

O(cost) 우리에게 코드를 표시한다 명확하다? – Jason

Java로 구현하기 전에 의사 코드를 작성하고 있으며 BreakPoints가 무작위 인 시점을 더 이상 알지 못합니다. 원하는 경우 공유 할 수 있습니다 – daydreamer

결과 배열의 트리와 각 리프가 아닌 노드의 비용을 작성할 수 있습니까? 따라서 현재 요소 6을 포함하고있는 배열을 포함하는 노드를 찾는 것이 어려워서는 안됩니다. – Thomas

죄송합니다, 루아이지만, 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

은 시간 복잡도가

출처

2014-05-13 17:54:21

동적 프로그래밍 문자열 깨기

답변

관련 문제