Re: How to slove it with DP? O(n^3)??
Posted by
tbtbtb 5 Apr 2004 10:58
Is it right??
for s:=n downto 1 do
begin
d[s,1,1]:=0;
d[s,1,0]:=0;
for L:=2 to n+1-s do
begin
d[s,L,0]:=min(dis(s,s+1)+d[s+1,L-1,0],dis(s,s+L-1)+d[s+1,L-1,1]);
d[s,L,1]:=min(dis(s+L-1,s+L-2)+d[s,L-1,1],dis(s+L-1,s)+d[s,L-1,0]);
end;
end;
end;
