Optimize matrix chain multiplication
Ruby, 176 172 205 characters
Here is another version (several chars longer) which will also run for large input in reasonable time.
q=(gets.split&lt;&lt;$_[/\d+$/]).map &amp;:to_i
r=Hash.new{|h,i|h[i]=Hash.new{|h,j|h[j]=1e12;h[j]=i==j ?[0,[]]:(i...j).map{|k|a,c=r[i][k];b,d=r[k+1][j];[a+b+q[i-1]*q[k]*q[j],c+d+[k]]}.min}}
$&gt;&lt;&lt;r[1][q.size-1][1]*' '

First version: straight recursive implementation in Ruby. It does a complete search and thus might be slow on large inputs.
k=-&gt;m{m[2]?(1..m.size-2).map{|l|s=k[m[0,l]+m[l+1..-1]];[m[l-1]*m[l]*m[l+1]+s[0],[l]+s[1].map{|u|u&lt;l ?u:u+1}]}.min: [0,[]]}
$&gt;&lt;&lt;k[(gets.split&lt;&lt;$_[/\d+$/]).map &amp;:to_i][1]*' '