<p>There are <code>n</code> piles of <code>stones</code> arranged in a row. The <code>i<sup>th</sup></code> pile has <code>stones[i]</code> stones.</p>

<p>A move consists of merging exactly <code>k</code> <strong>consecutive</strong> piles into one pile, and the cost of this move is equal to the total number of stones in these <code>k</code> piles.</p>

<p>Return <em>the minimum cost to merge all piles of stones into one pile</em>. If it is impossible, return <code>-1</code>.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<pre>
<strong>Input:</strong> stones = [3,2,4,1], k = 2
<strong>Output:</strong> 20
<strong>Explanation:</strong> We start with [3, 2, 4, 1].
We merge [3, 2] for a cost of 5, and we are left with [5, 4, 1].
We merge [4, 1] for a cost of 5, and we are left with [5, 5].
We merge [5, 5] for a cost of 10, and we are left with [10].
The total cost was 20, and this is the minimum possible.
</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> stones = [3,2,4,1], k = 3
<strong>Output:</strong> -1
<strong>Explanation:</strong> After any merge operation, there are 2 piles left, and we can&#39;t merge anymore.  So the task is impossible.
</pre>

<p><strong class="example">Example 3:</strong></p>

<pre>
<strong>Input:</strong> stones = [3,5,1,2,6], k = 3
<strong>Output:</strong> 25
<strong>Explanation:</strong> We start with [3, 5, 1, 2, 6].
We merge [5, 1, 2] for a cost of 8, and we are left with [3, 8, 6].
We merge [3, 8, 6] for a cost of 17, and we are left with [17].
The total cost was 25, and this is the minimum possible.
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>n == stones.length</code></li>
	<li><code>1 &lt;= n &lt;= 30</code></li>
	<li><code>1 &lt;= stones[i] &lt;= 100</code></li>
	<li><code>2 &lt;= k &lt;= 30</code></li>
</ul>

class Solution:
    def mergeStones(self, stones: List[int], k: int) -> int:
        
        # at each step of the dp, refer to the inputs from subproblems as stones
        # and when you combine stones in the current problem, you get a pile,
        # which becomes a stone for the super-problem

        # dp(i, j, x) is the minimum cost to merge stones from
        # index i up to and including index j, resulting in x different piles

        # dp(i, j, 1) = dp(i, j, k) + sum(stones[i:j+1])
        # 1 pile is formed from k different stones
        # combining them into one pile costs the sum of the stones

        # dp(i, j, x) = dp(i, t, 1) + dp(t+1, j, x-1)
        # The first pile can be created from stones i to i <= t <= j-(x-1) stones,
        # so that there are k-1 stones left over to merge with

        # Base case:
        # dp(i, i, 1) = 0
        # since there's no merge to be performed, it doesn't cost anything

        # Also, we use prefix sums so we don't have to keep calculating sums

        n = len(stones)
        prefixSums = [stones[0]]
        for num in stones[1:]:
            prefixSums.append(num + prefixSums[-1])

        # @cache
        # def dp(i, j, x):
        #     if i == j:
        #         return 0 if x == 1 else float('inf')

        #     if x == 1:
        #         return dp(i, j, k) + prefixSums[j] - (prefixSums[i-1] if i-1 >= 0 else 0)

        #     ans = float('inf')
        #     for t in range(i, j-x+2):
        #         ans = min(ans, dp(i, t, 1) + dp(t+1, j, x-1))

        #     return ans

        # val = dp(0, n-1, 1)
        # return val if val != float('inf') else -1

        dp = [[[float('inf') for _ in range(k+1)] for _ in range(n+1)] for _ in range(n+1)]
        for i in range(n+1):
            dp[i][i][1] = 0

        for size in range(1, n):
            for i in range(n-size):
                j = i + size

                for x in range(2, k+1):                    
                    for t in range(i, j-x+2):
                        dp[i][j][x] = min(dp[i][j][x], dp[i][t][1] + dp[t+1][j][x-1])

                dp[i][j][1] = dp[i][j][k] + prefixSums[j] - (prefixSums[i-1] if i-1 >= 0 else 0)
        
        return dp[0][n-1][1] if dp[0][n-1][1] != float('inf') else -1
17700