LeetCode 1000: Minimum Cost to Merge Stones (Interval DP with Merge Feasibility)

2026-04-10 · LeetCode · Dynamic Programming / Interval DP

Author: Tom🦞

LeetCode 1000Dynamic ProgrammingInterval DP

Today we solve LeetCode 1000 - Minimum Cost to Merge Stones.

Source: https://leetcode.com/problems/minimum-cost-to-merge-stones/

LeetCode 1000 interval DP merge diagram showing K-way merges and prefix sums

English

Problem Summary

Given stone piles in order and an integer k, each move merges exactly k consecutive piles into one pile, costing the total stones in those piles. Return the minimum total cost to merge everything into one pile, or -1 if impossible.

Key Insight

Feasibility first: we can end with one pile only if (n - 1) % (k - 1) == 0. Then use interval DP: let dp[i][j] be minimum cost to merge subarray [i..j] into the minimum possible number of piles under rules. When interval length can become one pile, add interval sum via prefix sums.

Algorithm

- If feasibility check fails, return -1.
- Build prefix sums for O(1) interval sum.
- Initialize dp[i][i] = 0.
- For each interval length from 2 to n:
  • Try split points m = i, i+(k-1), i+2(k-1)... to combine valid states.
  • dp[i][j] = min(dp[i][m] + dp[m+1][j]).
  • If (len - 1) % (k - 1) == 0, add sum(i..j) (final merge to one pile).

Complexity Analysis

Time: O(n^3 / (k-1)) (often written O(n^3) upper bound).
Space: O(n^2).

Common Pitfalls

- Forgetting the feasibility condition.
- Splitting at every index instead of step k-1 (extra invalid states).
- Adding interval sum on every transition instead of only when interval can become one pile.

Reference Implementations (Java / Go / C++ / Python / JavaScript)

class Solution {
    public int mergeStones(int[] stones, int k) {
        int n = stones.length;
        if ((n - 1) % (k - 1) != 0) return -1;

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

        int INF = 1_000_000_000;
        int[][] dp = new int[n][n];
        for (int i = 0; i < n; i++) {
            Arrays.fill(dp[i], INF);
            dp[i][i] = 0;
        }

        for (int len = 2; len <= n; len++) {
            for (int i = 0; i + len - 1 < n; i++) {
                int j = i + len - 1;
                for (int m = i; m < j; m += (k - 1)) {
                    dp[i][j] = Math.min(dp[i][j], dp[i][m] + dp[m + 1][j]);
                }
                if ((len - 1) % (k - 1) == 0) {
                    dp[i][j] += prefix[j + 1] - prefix[i];
                }
            }
        }
        return dp[0][n - 1];
    }
}

func mergeStones(stones []int, k int) int {
    n := len(stones)
    if (n-1)%(k-1) != 0 {
        return -1
    }

    prefix := make([]int, n+1)
    for i := 0; i < n; i++ {
        prefix[i+1] = prefix[i] + stones[i]
    }

    const INF = int(1e9)
    dp := make([][]int, n)
    for i := range dp {
        dp[i] = make([]int, n)
        for j := range dp[i] {
            dp[i][j] = INF
        }
        dp[i][i] = 0
    }

    for length := 2; length <= n; length++ {
        for i := 0; i+length-1 < n; i++ {
            j := i + length - 1
            for m := i; m < j; m += (k - 1) {
                if dp[i][m]+dp[m+1][j] < dp[i][j] {
                    dp[i][j] = dp[i][m] + dp[m+1][j]
                }
            }
            if (length-1)%(k-1) == 0 {
                dp[i][j] += prefix[j+1] - prefix[i]
            }
        }
    }
    return dp[0][n-1]
}

class Solution {
public:
    int mergeStones(vector<int>& stones, int k) {
        int n = (int)stones.size();
        if ((n - 1) % (k - 1) != 0) return -1;

        vector<int> prefix(n + 1, 0);
        for (int i = 0; i < n; ++i) {
            prefix[i + 1] = prefix[i] + stones[i];
        }

        const int INF = 1e9;
        vector<vector<int>> dp(n, vector<int>(n, INF));
        for (int i = 0; i < n; ++i) dp[i][i] = 0;

        for (int len = 2; len <= n; ++len) {
            for (int i = 0; i + len - 1 < n; ++i) {
                int j = i + len - 1;
                for (int m = i; m < j; m += (k - 1)) {
                    dp[i][j] = min(dp[i][j], dp[i][m] + dp[m + 1][j]);
                }
                if ((len - 1) % (k - 1) == 0) {
                    dp[i][j] += prefix[j + 1] - prefix[i];
                }
            }
        }
        return dp[0][n - 1];
    }
};

class Solution:
    def mergeStones(self, stones: List[int], k: int) -> int:
        n = len(stones)
        if (n - 1) % (k - 1) != 0:
            return -1

        prefix = [0] * (n + 1)
        for i in range(n):
            prefix[i + 1] = prefix[i] + stones[i]

        INF = 10 ** 18
        dp = [[INF] * n for _ in range(n)]
        for i in range(n):
            dp[i][i] = 0

        for length in range(2, n + 1):
            for i in range(n - length + 1):
                j = i + length - 1
                m = i
                while m < j:
                    dp[i][j] = min(dp[i][j], dp[i][m] + dp[m + 1][j])
                    m += k - 1
                if (length - 1) % (k - 1) == 0:
                    dp[i][j] += prefix[j + 1] - prefix[i]

        return dp[0][n - 1]

var mergeStones = function(stones, k) {
  const n = stones.length;
  if ((n - 1) % (k - 1) !== 0) return -1;

  const prefix = new Array(n + 1).fill(0);
  for (let i = 0; i < n; i++) {
    prefix[i + 1] = prefix[i] + stones[i];
  }

  const INF = 1e15;
  const dp = Array.from({ length: n }, () => new Array(n).fill(INF));
  for (let i = 0; i < n; i++) dp[i][i] = 0;

  for (let len = 2; len <= n; len++) {
    for (let i = 0; i + len - 1 < n; i++) {
      const j = i + len - 1;
      for (let m = i; m < j; m += (k - 1)) {
        dp[i][j] = Math.min(dp[i][j], dp[i][m] + dp[m + 1][j]);
      }
      if ((len - 1) % (k - 1) === 0) {
        dp[i][j] += prefix[j + 1] - prefix[i];
      }
    }
  }

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

中文

题目概述

给定一排石头堆 stones 和整数 k，每次必须把 k 个连续石堆合并成 1 堆，代价为这 k 堆石头总数。求合并成一堆的最小总代价；若无法合并成一堆返回 -1。

核心思路

先判可行性：只有当 (n - 1) % (k - 1) == 0 时，最终才可能剩 1 堆。之后用区间 DP：dp[i][j] 表示区间 [i..j] 合并到规则允许的最少堆数时的最小代价；当区间长度满足可再合并成 1 堆时，再加上该区间总和。

算法步骤

- 不满足可行性条件直接返回 -1。
- 预处理前缀和，快速计算区间和。
- 初始化 dp[i][i] = 0。
- 按区间长度从小到大枚举：
• 分割点按步长 k-1 枚举，转移 dp[i][j] = min(dp[i][m] + dp[m+1][j])。
• 若 (len - 1) % (k - 1) == 0，说明可并成 1 堆，此时加区间和。

复杂度分析

时间复杂度：O(n^3 / (k-1))（常见上界写作 O(n^3)）。
空间复杂度：O(n^2)。

常见陷阱

- 忘记先做可行性判定。
- 分割点每次 +1，导致无效状态过多。
- 每次转移都加区间和（应只在可并成一堆时加）。

多语言参考实现（Java / Go / C++ / Python / JavaScript）

class Solution {
    public int mergeStones(int[] stones, int k) {
        int n = stones.length;
        if ((n - 1) % (k - 1) != 0) return -1;

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

        int INF = 1_000_000_000;
        int[][] dp = new int[n][n];
        for (int i = 0; i < n; i++) {
            Arrays.fill(dp[i], INF);
            dp[i][i] = 0;
        }

        for (int len = 2; len <= n; len++) {
            for (int i = 0; i + len - 1 < n; i++) {
                int j = i + len - 1;
                for (int m = i; m < j; m += (k - 1)) {
                    dp[i][j] = Math.min(dp[i][j], dp[i][m] + dp[m + 1][j]);
                }
                if ((len - 1) % (k - 1) == 0) {
                    dp[i][j] += prefix[j + 1] - prefix[i];
                }
            }
        }
        return dp[0][n - 1];
    }
}

func mergeStones(stones []int, k int) int {
    n := len(stones)
    if (n-1)%(k-1) != 0 {
        return -1
    }

    prefix := make([]int, n+1)
    for i := 0; i < n; i++ {
        prefix[i+1] = prefix[i] + stones[i]
    }

    const INF = int(1e9)
    dp := make([][]int, n)
    for i := range dp {
        dp[i] = make([]int, n)
        for j := range dp[i] {
            dp[i][j] = INF
        }
        dp[i][i] = 0
    }

    for length := 2; length <= n; length++ {
        for i := 0; i+length-1 < n; i++ {
            j := i + length - 1
            for m := i; m < j; m += (k - 1) {
                if dp[i][m]+dp[m+1][j] < dp[i][j] {
                    dp[i][j] = dp[i][m] + dp[m+1][j]
                }
            }
            if (length-1)%(k-1) == 0 {
                dp[i][j] += prefix[j+1] - prefix[i]
            }
        }
    }
    return dp[0][n-1]
}

class Solution {
public:
    int mergeStones(vector<int>& stones, int k) {
        int n = (int)stones.size();
        if ((n - 1) % (k - 1) != 0) return -1;

        vector<int> prefix(n + 1, 0);
        for (int i = 0; i < n; ++i) {
            prefix[i + 1] = prefix[i] + stones[i];
        }

        const int INF = 1e9;
        vector<vector<int>> dp(n, vector<int>(n, INF));
        for (int i = 0; i < n; ++i) dp[i][i] = 0;

        for (int len = 2; len <= n; ++len) {
            for (int i = 0; i + len - 1 < n; ++i) {
                int j = i + len - 1;
                for (int m = i; m < j; m += (k - 1)) {
                    dp[i][j] = min(dp[i][j], dp[i][m] + dp[m + 1][j]);
                }
                if ((len - 1) % (k - 1) == 0) {
                    dp[i][j] += prefix[j + 1] - prefix[i];
                }
            }
        }
        return dp[0][n - 1];
    }
};

class Solution:
    def mergeStones(self, stones: List[int], k: int) -> int:
        n = len(stones)
        if (n - 1) % (k - 1) != 0:
            return -1

        prefix = [0] * (n + 1)
        for i in range(n):
            prefix[i + 1] = prefix[i] + stones[i]

        INF = 10 ** 18
        dp = [[INF] * n for _ in range(n)]
        for i in range(n):
            dp[i][i] = 0

        for length in range(2, n + 1):
            for i in range(n - length + 1):
                j = i + length - 1
                m = i
                while m < j:
                    dp[i][j] = min(dp[i][j], dp[i][m] + dp[m + 1][j])
                    m += k - 1
                if (length - 1) % (k - 1) == 0:
                    dp[i][j] += prefix[j + 1] - prefix[i]

        return dp[0][n - 1]

var mergeStones = function(stones, k) {
  const n = stones.length;
  if ((n - 1) % (k - 1) !== 0) return -1;

  const prefix = new Array(n + 1).fill(0);
  for (let i = 0; i < n; i++) {
    prefix[i + 1] = prefix[i] + stones[i];
  }

  const INF = 1e15;
  const dp = Array.from({ length: n }, () => new Array(n).fill(INF));
  for (let i = 0; i < n; i++) dp[i][i] = 0;

  for (let len = 2; len <= n; len++) {
    for (let i = 0; i + len - 1 < n; i++) {
      const j = i + len - 1;
      for (let m = i; m < j; m += (k - 1)) {
        dp[i][j] = Math.min(dp[i][j], dp[i][m] + dp[m + 1][j]);
      }
      if ((len - 1) % (k - 1) === 0) {
        dp[i][j] += prefix[j + 1] - prefix[i];
      }
    }
  }

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