DiffPush Tier Dynamic Programming · DP on Partition O(N^3) · O(N^2)
A graphics engine chains a sequence of image transforms whose intermediate buffers have known dimensions. Applying transforms in different groupings changes how many pixel-multiply operations the GPU performs, since pairing buffers incurs a cost proportional to their shared edges. The pipeline tuner must pick the association order that minimizes total scalar work.
Input: An integer N and an array arr of N integers, where matrix i has dimensions arr[i-1] x arr[i] (so there are N-1 matrices).
Output: Return the minimum number of scalar multiplications needed to multiply the whole chain.
2 <= N <= 1001 <= arr[i] <= 500Input: {"N":5,"arr":[40,20,30,10,30]}
Output: 26000
Grouping (A*(B*C))*D bills 6000 + 8000 + 12000 = 26000 operations.
Input: {"N":4,"arr":[10,15,20,25]}
Output: 8000
(A*B)*C costs 10*15*20 + 10*20*25 = 8000, beating the other association's 11250.