Matrix chain multiplication: Difference between revisions

Content added Content deleted
m (→‎Python: actually, while the function is indeed recursive, this is not a recursive generator (no "yield from" inside aux))
Line 30: Line 30:
We will solve the task in three steps:
We will solve the task in three steps:


1) Enumerate all ways to parenthesize (in a recursive generator), and for each one compute the cost. Then simply look up the minimal cost.
1) Enumerate all ways to parenthesize (using a generator to save space), and for each one compute the cost. Then simply look up the minimal cost.


2) Merge the enumeration and the cost function in a recursive cost optimizing function. The computation is roughly the same, but it's much faster as some steps are removed.
2) Merge the enumeration and the cost function in a recursive cost optimizing function. The computation is roughly the same, but it's much faster as some steps are removed.
Retrieved from "https://rosettacode.org/wiki/Matrix_chain_multiplication"