Go backward to Sequential Algorithm Go up to Top Go forward to Optimization

Observation

MatMin has same structure as matrix multiplication (+ -> min, * -> +).

• Define D ×W = MatMult(D,W)
• Begin: D₁ = W
• General: D_i = D^i-1 ×W = Wⁱ
• End: D = D_n-1 = W^n-1

Problem solution is essentially repeated matrix multiplication!