0. Problem

We want minCost(merging all the hay bales).

1. Recursion

At first, it's not clear what the recursion should be. But recursion always starts by breaking down the very end result, so we'll start by trying to write the very end result recursively.

The end result here is when we merge the last two hay bales. We already merged everything that's been circled in black, and all we need to do now is merge the final two hay bales.

The min cost of merging the last two hay bales is just:

To turn this into math, we can just use this:

The equation becomes:

Remember, everything we did above applied to the last 2 hay bales. Now we want to make sure it works in general, for any i and j. Consider the following i and j:

The cost of merging is just the cost of merging the two big hay bales, plus the cost of getting the initial hay bales. So the above recursion works in general, even though it didn't have to.

2. Base case

We need to stop recursing when we get to the the smallest possible interval size. The smallest interval that happens is when k=i or k=j-1. In either case, we call minCost(i, i), or minCost(j, j). Our base case is:

3. Code

This is another DP problem. We just need to compute small intervals first, and big ones last.

Time Complexity $O(n^3)$. We iterate over all $O(n^2)$ intervals and do an $O(n)$ operation to find the min at each interval.

Space Complexity $O(n^2)$ for the $n\times n$ array.