**Problem**

Consider we have a complete directed acyclic graph of $n$ vertices, such that the topological sort order is $v_1,\ldots,v_n$. There is a weight function $w(v_i,v_j)$, such that it has the Monge property, i.e. $w(v_i,v_j) + w(v_{i+1},v_{j + 1}) \leq w(v_i,v_{j+1}) + w(v_{i+1},v_{j})$ holds for all $1 < i + 1 < j \leq n$.

The weight of a path is the sum of the weight of all edges in the path. We want to find a path of length $k$ from $v_1$ to $v_n$, such that the weight is minimized.

The function would have the signature minWeightKLinkedPath :: (Integral a, Num b)=>a->a->(a->a->b)->[a]. The input is $n$, $k$, $w$ and the output is a minimum weight path of length $k$.

Solve the problem in $O(kn)$ time.

**Hint**

There is an algorithm to solve it in $O(k(n+m))$ time on stackoverflow, which can be modified to run in $O(kn^2)$ time.

Apply the technique in the talk Revisiting The Monge Property. The exercise on totally monotone matrices already implemented the subroutine!

**Extensions**

We can actually implement the most general form of the problem in Revisiting The Monge Property, and also reduce the memory usage from $O(kn)$ to $O(n)$. Looks like no one has done it with Haskell yet.

**Applications**

Consider the linear partition problem that got featured on hacker news. It can be reduced to this problem and produce a $O(kn)$ time solution. In the application $k$ is just $cn$ for some constant $c$, thus in theory there is a even better (in theory) solution that takes $n2^{O(\sqrt{\log k \log \log n})}$ time discovered by Schieber.

# Solution

```
minWeightkEdgePath :: (Ord a, Num a) => Int -> Int -> (Int -> Int -> a) -> [Int]
minWeightkEdgePath k n w = backtrack (k-1) n
where
backtrack (-1) _ = []
backtrack x y = y':backtrack (x-1) y'
where y' = snd (d!(x,y))
d = array ((0,0),(k-1,n)) [ ((i,j), f i j) | i<-[0..k-1],j<-[0..n]]
f 0 i = (w 0 i,0)
-- uncomment the following line to use the slower algorithm
-- f k i = minimum [(m k j i, j)|j<-[0..n]]
f k i = (m k j i,j)
where j = p!(k,i)
p = array ((1,0),(k,n)) [((z,i),t) |z<-[1..k],(i,t)<-zip [0..n] (columnMinima (m z) (n+1) (n+1))]
m k j i = fst (d!(k-1,j)) + w j i
```