257. Minimum Cost to Merge Stones

🔗 LeetCode Problem: 1000. Minimum Cost to Merge Stones
📊 Difficulty: Hard
🏷️ Topics: Array, Dynamic Programming, Interval DP

Problem Statement

There are n piles of stones arranged in a row. The ith pile has stones[i] stones.

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

Return the minimum cost to merge all piles of stones into one pile. If it is impossible, return -1.

Example 1:

Input: stones = [3,2,4,1], k = 2
Output: 20
Explanation: 
Merge [3,2] for cost 5 → [5,4,1]
Merge [4,1] for cost 5 → [5,5]
Merge [5,5] for cost 10 → [10]
Total: 5+5+10 = 20

Example 2:

Input: stones = [3,2,4,1], k = 3
Output: -1
Explanation: After merging, we'll have 2 piles, can't merge with k=3

Example 3:

Input: stones = [3,5,1,2,6], k = 3
Output: 25
Explanation:
Merge [5,1,2] for cost 8 → [3,8,6]
Merge [3,8,6] for cost 17 → [17]
Total: 8+17 = 25

Constraints: - n == stones.length - 1 <= n <= 30 - 1 <= stones[i] <= 100 - 2 <= k <= 30

---

🌳 Visual Understanding - A Complex Merging Problem

The Critical First Question: Is It Even Possible?

Before we try to minimize cost, can we merge n piles into 1?

Key insight: Each merge reduces pile count by (k-1)
  Start: n piles
  After 1 merge: n - (k-1) piles
  After 2 merges: n - 2(k-1) piles
  ...
  Final: 1 pile

For this to work:
  n - m(k-1) = 1  for some integer m
  m(k-1) = n - 1
  (n-1) must be divisible by (k-1)

Formula: (n-1) % (k-1) == 0

Example 1: n=4, k=2
  (4-1) % (2-1) = 3 % 1 = 0 ✓ Possible!

Example 2: n=4, k=3  
  (4-1) % (3-1) = 3 % 2 = 1 ✗ Impossible!
  4 piles → 2 piles (stuck!)

Example 3: n=5, k=3
  (5-1) % (3-1) = 4 % 2 = 0 ✓ Possible!
  5 piles → 3 piles → 1 pile

THIS IS THE FIRST CHECK! 🔑

Visual Discovery - Why Order Matters (k=2):

stones = [3,2,4,1], k = 2

━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
Strategy 1: Merge leftmost pairs
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━

Step 1: [3,2,4,1] → merge [3,2]
        Cost: 3+2 = 5
        Result: [5,4,1]

Step 2: [5,4,1] → merge [5,4]
        Cost: 5+4 = 9
        Result: [9,1]

Step 3: [9,1] → merge [9,1]
        Cost: 9+1 = 10
        Result: [10]

Total cost: 5 + 9 + 10 = 24

━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
Strategy 2: Merge rightmost first
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━

Step 1: [3,2,4,1] → merge [4,1]
        Cost: 4+1 = 5
        Result: [3,2,5]

Step 2: [3,2,5] → merge [3,2]
        Cost: 3+2 = 5
        Result: [5,5]

Step 3: [5,5] → merge [5,5]
        Cost: 5+5 = 10
        Result: [10]

Total cost: 5 + 5 + 10 = 20 ✓ BETTER!

Different merge order = different total cost!
We need DP to find the optimal order! 🎯

Complex Example - Why This is HARD (k=3):

stones = [3,5,1,2,6], k = 3
n = 5, check: (5-1) % (3-1) = 4 % 2 = 0 ✓ Possible

Multiple strategies possible:

Strategy A: [3,5,1,2,6]
  Merge [3,5,1] cost=9 → [9,2,6]
  Merge [9,2,6] cost=17 → [17]
  Total: 9 + 17 = 26

Strategy B: [3,5,1,2,6]
  Merge [5,1,2] cost=8 → [3,8,6]
  Merge [3,8,6] cost=17 → [17]
  Total: 8 + 17 = 25 ✓ BETTER!

Strategy C: [3,5,1,2,6]
  Merge [1,2,6] cost=9 → [3,5,9]
  Merge [3,5,9] cost=17 → [17]
  Total: 9 + 17 = 26

Need to try ALL possibilities systematically!
This requires 3D DP! 🔥

The Core Challenge:

This is HARD because:

1. Must merge EXACTLY k consecutive piles
2. Order of merges affects total cost
3. Need to track: [start, end, num_piles]
4. 3D state space: dp[i][j][p]
5. Complex recurrence relation

This is one of the most challenging DP problems!
Combines interval DP with partition DP! 💪

---

🧠 Discovering the Solution - Building Deep Intuition

Question 1: What are we really asking?

Main problem: Merge stones[0..n-1] into 1 pile

But to get there, we need intermediate steps!

Subproblem: What's the minimum cost to merge stones[i..j] into p piles?

Why p piles?
  To merge into 1 pile, we first need k piles
  To get k piles, we might need different numbers of piles

This leads to 3D DP:
  dp[i][j][p] = min cost to merge stones[i..j] into exactly p piles

This is THE key insight! 🔑

Question 2: What's the recursive structure?

To merge stones[i..j] into p piles:

Case 1: p = 1 (merge into single pile)
  First merge into k piles
  Then merge those k piles into 1

  dp[i][j][1] = dp[i][j][k] + sum(stones[i..j])

  Why? The final merge of k piles costs sum of all stones!

Case 2: p > 1 (merge into p piles)
  Split range [i..j] into:
    - Left part: merge into 1 pile
    - Right part: merge into (p-1) piles

  Try all split points!

  dp[i][j][p] = min(dp[i][mid][1] + dp[mid+1][j][p-1])
                for valid mid values

Base case:
  dp[i][i][1] = 0 (single stone is already 1 pile)
  dp[i][i][p] = impossible for p > 1

Question 3: Why do we increment mid by (k-1)?

This is SUBTLE and important!

When we split into "1 pile" + "p-1 piles":
  The "1 pile" part must be achievable!

  stones[i..mid] can be merged into 1 pile only if:
    (mid - i) % (k-1) == 0

  This means: mid = i, i+(k-1), i+2(k-1), ...

  We increment by (k-1) to only try valid splits!

Example: k=3, trying to merge [0..6]
  Valid mid: 0, 2, 4, 6
  Not valid: 1, 3, 5 (can't merge into 1 pile)

This optimization is crucial! ✓

Question 4: Why prefix sum?

We compute sum(stones[i..j]) many times!

Precompute:
  prefix[i] = sum of stones[0..i-1]

Range sum:
  sum(stones[i..j]) = prefix[j+1] - prefix[i]

This is O(1) instead of O(n)!
Essential optimization for this problem.

---

🟢 Approach 1: Brute Force Recursion

💡 Intuition

Try all possible ways to partition and merge:
  - Try all split points
  - Recursively solve left and right
  - Take minimum cost

Pure recursion to understand the structure!

📝 Implementation

class Solution {
    private int[] prefixSum;

    public int mergeStones(int[] stones, int k) {
        int n = stones.length;

        // Check if possible
        if ((n - 1) % (k - 1) != 0) {
            return -1;
        }

        // Build prefix sum
        prefixSum = new int[n + 1];
        for (int i = 0; i < n; i++) {
            prefixSum[i + 1] = prefixSum[i] + stones[i];
        }

        // Solve: merge stones[0..n-1] into 1 pile
        return solve(stones, 0, n - 1, 1, k);
    }

    private int solve(int[] stones, int i, int j, int p, int k) {
        // Base case: single stone
        if (i == j) {
            return p == 1 ? 0 : Integer.MAX_VALUE;
        }

        // Merge into 1 pile
        if (p == 1) {
            int cost = solve(stones, i, j, k, k);
            if (cost == Integer.MAX_VALUE) {
                return Integer.MAX_VALUE;
            }
            // Final merge of k piles costs sum of all stones
            return cost + (prefixSum[j + 1] - prefixSum[i]);
        }

        // Merge into p piles (p > 1)
        int minCost = Integer.MAX_VALUE;

        // Try all split points (increment by k-1)
        for (int mid = i; mid < j; mid += (k - 1)) {
            int left = solve(stones, i, mid, 1, k);
            int right = solve(stones, mid + 1, j, p - 1, k);

            if (left != Integer.MAX_VALUE && right != Integer.MAX_VALUE) {
                minCost = Math.min(minCost, left + right);
            }
        }

        return minCost;
    }
}

🔍 Dry Run - Example: stones = [3,2,4,1], k = 2

Input: stones = [3,2,4,1], k = 2

━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
Check Possibility
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━

n = 4, k = 2
(n-1) % (k-1) = (4-1) % (2-1) = 3 % 1 = 0 ✓ Possible!

━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
Build Prefix Sum
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━

prefixSum = [0, 3, 5, 9, 10]

sum(0,3) = prefixSum[4] - prefixSum[0] = 10 - 0 = 10
sum(1,2) = prefixSum[3] - prefixSum[1] = 9 - 3 = 6

━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
Recursion Tree (simplified key path)
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━

solve(0, 3, 1, 2):  // Merge [3,2,4,1] into 1 pile
  p=1, so first merge into k=2 piles

  Call: solve(0, 3, 2, 2)  // into 2 piles

    Try mid=0: [3] + [2,4,1]
      left = solve(0, 0, 1, 2) = 0 (base case)
      right = solve(1, 3, 1, 2):  // [2,4,1] into 1
        First into k=2:
          solve(1, 3, 2, 2):
            Try mid=1: [2] + [4,1]
              left = 0
              right = solve(2, 3, 1, 2):
                solve(2, 3, 2, 2):
                  mid=2: [4] + [1]
                  left=0, right=0
                  return 0
                cost = 0 + sum(2,3) = 0 + 5 = 5
                return 5
              cost = 0 + 5 = 5

            Try mid=2: [2,4] + [1]
              left = solve(1, 2, 1, 2):
                solve(1, 2, 2, 2):
                  mid=1: [2] + [4]
                  return 0
                cost = 0 + 6 = 6
              right = 0
              cost = 6 + 0 = 6

            return min(5, 6) = 5

        cost = 5 + sum(1,3) = 5 + 7 = 12
        return 12

      cost = 0 + 12 = 12

    Try mid=1: [3,2] + [4,1]
      left = solve(0, 1, 1, 2):
        solve(0, 1, 2, 2): return 0
        cost = 0 + 5 = 5
      right = solve(2, 3, 1, 2) = 5 (computed above)
      cost = 5 + 5 = 10

    Try mid=2: [3,2,4] + [1]
      left = solve(0, 2, 1, 2):
        ... similar computation ... = 11
      right = 0
      cost = 11 + 0 = 11

    return min(12, 10, 11) = 10

  cost = 10 + sum(0,3) = 10 + 10 = 20

  return 20 ✓

Answer: 20

📊 Complexity Analysis

Time Complexity: Exponential

Without memoization, explores all possible partitions
Many overlapping subproblems computed multiple times

Space Complexity: O(n)

Recursion stack depth
Prefix sum array

---

🟡 Approach 2: Top-Down DP (Memoization)

💡 Intuition

Same recursive structure, but cache results!

Key: dp[i][j][p] computed once and reused

Use 3D memoization array
Or use HashMap with key encoding

📝 Implementation

class Solution {
    private int[] prefixSum;
    private Integer[][][] memo;

    public int mergeStones(int[] stones, int k) {
        int n = stones.length;

        // Check if possible
        if ((n - 1) % (k - 1) != 0) {
            return -1;
        }

        // Build prefix sum
        prefixSum = new int[n + 1];
        for (int i = 0; i < n; i++) {
            prefixSum[i + 1] = prefixSum[i] + stones[i];
        }

        // Memoization table
        memo = new Integer[n][n][k + 1];

        return solveMemo(stones, 0, n - 1, 1, k);
    }

    private int solveMemo(int[] stones, int i, int j, int p, int k) {
        // Base case
        if (i == j) {
            return p == 1 ? 0 : Integer.MAX_VALUE;
        }

        // Check memo
        if (memo[i][j][p] != null) {
            return memo[i][j][p];
        }

        int result;

        // Merge into 1 pile
        if (p == 1) {
            int cost = solveMemo(stones, i, j, k, k);
            if (cost == Integer.MAX_VALUE) {
                result = Integer.MAX_VALUE;
            } else {
                result = cost + (prefixSum[j + 1] - prefixSum[i]);
            }
        } else {
            // Merge into p piles
            int minCost = Integer.MAX_VALUE;

            for (int mid = i; mid < j; mid += (k - 1)) {
                int left = solveMemo(stones, i, mid, 1, k);
                int right = solveMemo(stones, mid + 1, j, p - 1, k);

                if (left != Integer.MAX_VALUE && right != Integer.MAX_VALUE) {
                    minCost = Math.min(minCost, left + right);
                }
            }

            result = minCost;
        }

        memo[i][j][p] = result;
        return result;
    }
}

📊 Complexity Analysis

Time Complexity: O(n³ * k / (k-1))

States: O(n² * k) for dp[i][j][p]
Each state: O(n / (k-1)) for loop (mid increments by k-1)
Total: O(n³ * k / (k-1))

Space Complexity: O(n² * k)

Memoization table: n × n × k
Recursion stack: O(n)
Total: O(n² * k)

---

🟢 Approach 3: Bottom-Up DP (Tabulation)

💡 Intuition

Build solution iteratively!

Process by interval length (small to large)
For each interval and each p, compute optimal cost

No recursion needed!

📝 Implementation

class Solution {
    public int mergeStones(int[] stones, int k) {
        int n = stones.length;

        // Check if possible
        if ((n - 1) % (k - 1) != 0) {
            return -1;
        }

        // Build prefix sum
        int[] prefixSum = new int[n + 1];
        for (int i = 0; i < n; i++) {
            prefixSum[i + 1] = prefixSum[i] + stones[i];
        }

        // DP table: dp[i][j][p] = min cost to merge stones[i..j] into p piles
        int[][][] dp = new int[n][n][k + 1];

        // Initialize with large values
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                for (int p = 0; p <= k; p++) {
                    dp[i][j][p] = Integer.MAX_VALUE;
                }
            }
        }

        // Base case: single stone
        for (int i = 0; i < n; i++) {
            dp[i][i][1] = 0;
        }

        // Build table by interval length
        for (int len = 2; len <= n; len++) {
            for (int i = 0; i <= n - len; i++) {
                int j = i + len - 1;

                // Try merging into p piles (p from 2 to k)
                for (int p = 2; p <= k; p++) {
                    // Try all split points
                    for (int mid = i; mid < j; mid += (k - 1)) {
                        if (dp[i][mid][1] != Integer.MAX_VALUE && 
                            dp[mid + 1][j][p - 1] != Integer.MAX_VALUE) {
                            dp[i][j][p] = Math.min(dp[i][j][p],
                                dp[i][mid][1] + dp[mid + 1][j][p - 1]);
                        }
                    }
                }

                // Merge into 1 pile from k piles
                if (dp[i][j][k] != Integer.MAX_VALUE) {
                    dp[i][j][1] = dp[i][j][k] + (prefixSum[j + 1] - prefixSum[i]);
                }
            }
        }

        return dp[0][n - 1][1] == Integer.MAX_VALUE ? -1 : dp[0][n - 1][1];
    }
}

🔍 Complete Dry Run - Example: stones = [3,5,1], k = 3

Input: stones = [3,5,1], k = 3
n = 3, check: (3-1) % (3-1) = 2 % 2 = 0 ✓

━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
Prefix Sum
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━

prefixSum = [0, 3, 8, 9]

━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
Initialize Base Cases
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━

dp[0][0][1] = 0  (stone 3 is already 1 pile)
dp[1][1][1] = 0  (stone 5 is already 1 pile)
dp[2][2][1] = 0  (stone 1 is already 1 pile)

━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
Length 2
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━

Interval [0,1]: stones = [3,5]

  p=2: Try to merge into 2 piles
    mid=0: dp[0][0][1] + dp[1][1][1]
         = 0 + 0 = 0
    dp[0][1][2] = 0

  p=3: Can't have 3 piles from 2 stones
    dp[0][1][3] = ∞

  p=1: Merge 2 piles into 1 (need k=3 piles first)
    dp[0][1][1] = ∞ (can't get 3 piles from 2 stones)

Interval [1,2]: stones = [5,1]
  p=2: dp[1][2][2] = 0
  p=1: dp[1][2][1] = ∞

━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
Length 3
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━

Interval [0,2]: stones = [3,5,1]

  p=2: Try to merge into 2 piles
    mid=0: dp[0][0][1] + dp[1][2][1]
         = 0 + ∞ = ∞

    mid=2: (i + k-1 = 0 + 2 = 2)
         dp[0][2][1] not computed yet

    Skip for now

  p=3: Try to merge into 3 piles
    mid=0: dp[0][0][1] + dp[1][2][2]
         = 0 + 0 = 0
    dp[0][2][3] = 0

  p=1: Merge from k=3 piles
    dp[0][2][1] = dp[0][2][3] + sum(0,2)
                = 0 + (9 - 0)
                = 9 ✓

━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
RESULT
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━

dp[0][2][1] = 9

Meaning: Merge [3,5,1] into 3 piles (cost 0)
         Then merge those 3 into 1 (cost 3+5+1=9)
         Total: 9 ✓

📊 Complexity Analysis

Time Complexity: O(n³ * k / (k-1))

Three nested loops: len, i, mid
Plus p loop of k iterations
Total: O(n³ * k / (k-1))

Space Complexity: O(n² * k)

DP table: n × n × k
Prefix sum: O(n)
Total: O(n² * k)

---

🟢 Approach 4: Optimized Bottom-Up (2D DP)

💡 Intuition

Key observation: We only care about dp[i][j][1] finally!

Can we avoid computing all p values?

Optimization: Directly compute dp[i][j] = min cost to merge into 1 pile

This reduces from 3D to 2D!

📝 Implementation

class Solution {
    public int mergeStones(int[] stones, int k) {
        int n = stones.length;

        if ((n - 1) % (k - 1) != 0) {
            return -1;
        }

        // Prefix sum
        int[] prefixSum = new int[n + 1];
        for (int i = 0; i < n; i++) {
            prefixSum[i + 1] = prefixSum[i] + stones[i];
        }

        // 2D DP: dp[i][j] = min cost to maximally merge stones[i..j]
        int[][] dp = new int[n][n];

        for (int len = k; len <= n; len++) {
            for (int i = 0; i <= n - len; i++) {
                int j = i + len - 1;
                dp[i][j] = Integer.MAX_VALUE;

                for (int mid = i; mid < j; mid += (k - 1)) {
                    dp[i][j] = Math.min(dp[i][j], dp[i][mid] + dp[mid + 1][j]);
                }

                // If this interval can be merged into 1 pile, add final cost
                if ((len - 1) % (k - 1) == 0) {
                    dp[i][j] += (prefixSum[j + 1] - prefixSum[i]);
                }
            }
        }

        return dp[0][n - 1];
    }
}

📊 Complexity Analysis

Time Complexity: O(n³ / (k-1))

Reduced from 3D to 2D
More efficient!

Space Complexity: O(n²)

2D DP table
Much better than O(n² * k)!

---

🎯 Key Insights Summary

The Five Critical Points:

1. Possibility Check is ESSENTIAL

(n-1) % (k-1) == 0

This determines if solution exists!
Check FIRST before any DP! 🔑

2. 3D State Definition

dp[i][j][p] = min cost to merge stones[i..j] into p piles

Three dimensions essential:
  i, j: interval
  p: number of piles to merge into

3. Increment mid by (k-1)

Only certain split points are valid!
mid must allow left part to merge into 1 pile

Increment: mid += (k-1)
This is crucial optimization!

4. Prefix Sum Optimization

sum(stones[i..j]) computed many times

Precompute prefix sums: O(1) lookup
Essential for efficiency!

5. Can Optimize to 2D

3D DP: O(n² * k) space
2D DP: O(n²) space

2D version more space-efficient!

---

📝 Quick Revision Notes

🎯 Core Concept

Problem: Merge n piles into 1, each merge exactly k consecutive piles

Possibility Check:

(n-1) % (k-1) == 0

DP State (3D):

dp[i][j][p] = min cost to merge stones[i..j] into p piles

Recurrence:

p = 1: dp[i][j][1] = dp[i][j][k] + sum(stones[i..j])
p > 1: dp[i][j][p] = min(dp[i][mid][1] + dp[mid+1][j][p-1])
       for mid = i, i+(k-1), i+2(k-1), ...

🎪 Memory Aid

"Check possible, (n-1) mod (k-1)!"
"Three dimensions, state so stern!"
"Mid by k-1, valid splits discern!"
"Prefix sums, efficiency we earn!" ✨

---

🎉 Congratulations!

You've mastered Minimum Cost to Merge Stones - one of the hardest DP problems!

What You Learned:

✅ 3D DP - Multi-dimensional state space
✅ Interval DP - Processing ranges
✅ Possibility check - Mathematical constraint
✅ Incremental mid - Smart iteration
✅ Space optimization - 3D → 2D reduction

This problem combines interval DP with partition constraints - extremely valuable pattern for advanced problems! 🚀✨🎯