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:

minCost(merging all hay bales) = min over k (
    (cost of merging the two final hay bales)
    + minCost(first merging all hay bales from 0...k)
    + minCost(first merging all hay bales from k+1...n-1)
)

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

minCost(i, j) = the cost of merging i...j.

The equation becomes:

minCost(i, j) = min(
    sum(nums[i:j+1])
    + minCost(i, k)
    + minCost(k+1, j)
        for k in range(i, j) # k starts at i (the first hay bale merging with all the others), and k+1 goes up to j (the last hay bale merging with all the others), so i<=k<j.
)

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:

if i == j:
    return nums[x]

3. Code

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

def minCostToMerge(nums):

    # minCost[i][j]
    # starts out as all Nones, gets replaced as we iterate
    n = len(nums)
    minCost = [[None for _ in range(n)] for _ in range(n)]

    # length = interval size. First it's 0, then 1, 2, ...
    # start = the valid starting points for the interval of size `length`
    for length in range(0, n): 
        for start in range(0, n - length):
            i = start
            j = start + length
            
            # base case
            if i == j:
                minCost[i][j] = 0
                continue
            
            # recursion
            minCost[i][j] = sum(nums[i:j+1]) + min(
                + minCost[i][k]
                + minCost[k+1][j]
                    for k in range(i, j)
            )

    return minCost[0][n-1]

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.