It can be solved in O(n^2) time.

How?? Give me some hints?

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;