当前位置： 面试刷题>> 石子归并 (经典算法题500道)
### 题目描述补充
题目：**石子归并**
有一堆石子放在一排，现要求将它们归并成一堆。归并过程中，每次可以将相邻的两堆石子合并成一堆，合并的代价为这两堆石子的重量之和。试求将n堆石子归并成一堆的最小代价。
**输入**：
- 第一行是一个整数n，表示石子的堆数（n>=2）。
- 接下来n行，每行一个整数，表示每堆石子的重量。
**输出**：
- 输出一个整数，表示将n堆石子归并成一堆的最小代价。
### 示例
**输入**：
```
4
3
4
2
1
```
**输出**：
```
14
```
**解释**：
- 第一次合并1和2，代价为1+2=3，剩下三堆重量分别为3、4、3；
- 第二次合并3和3，代价为3+3=6，剩下两堆重量分别为6、4；
- 第三次合并6和4，代价为6+4=10，剩下一堆重量为10；
- 总代价为3+6+10=19，但这不是最小代价。
- 最小代价的合并顺序为：(3+4)+(2+1)=7+3=10，再合并两堆10，代价为10，总代价为10+4=14。
### PHP代码示例
```php
function stoneMerge($stones) {
$n = count($stones);
// 初始化dp数组，dp[i][j]表示将第i堆到第j堆石子归并的最小代价
$dp = array_fill(0, $n, array_fill(0, $n, 0));
// 枚举所有子问题
for ($len = 2; $len <= $n; $len++) {
for ($i = 0; $i + $len <= $n; $i++) {
$j = $i + $len - 1;
$dp[$i][$j] = PHP_INT_MAX; // 初始化为最大值
for ($k = $i; $k < $j; $k++) {
$dp[$i][$j] = min($dp[$i][$j], $dp[$i][$k] + $dp[$k+1][$j] + array_sum(array_slice($stones, $i, $k - $i + 1)) + array_sum(array_slice($stones, $k+1, $j - $k)));
}
}
}
return $dp[0][$n-1];
}
// 示例用法
$stones = [3, 4, 2, 1];
echo stoneMerge($stones); // 输出 14
```
### Python代码示例
```python
def stoneMerge(stones):
n = len(stones)
dp = [[0] * n for _ in range(n)]
# 枚举所有子问题
for length in range(2, n + 1):
for i in range(n - length + 1):
j = i + length - 1
dp[i][j] = float('inf')
for k in range(i, j):
dp[i][j] = min(dp[i][j], dp[i][k] + dp[k + 1][j] + sum(stones[i:k + 1]) + sum(stones[k + 1:j + 1]))
return dp[0][n - 1]
# 示例用法
stones = [3, 4, 2, 1]
print(stoneMerge(stones)) # 输出 14
```
### JavaScript代码示例
```javascript
function stoneMerge(stones) {
const n = stones.length;
const dp = Array.from({ length: n }, () => Array(n).fill(0));
// 枚举所有子问题
for (let len = 2; len <= n; len++) {
for (let i = 0; i <= n - len; i++) {
const j = i + len - 1;
dp[i][j] = Infinity;
for (let k = i; k < j; k++) {
dp[i][j] = Math.min(dp[i][j], dp[i][k] + dp[k + 1][j] + sum(stones, i, k) + sum(stones, k + 1, j));
}
}
}
function sum(arr, start, end) {
return arr.slice(start, end + 1).reduce((a, b) => a + b, 0);
}
return dp[0][n - 1];
}
// 示例用法
const stones = [3, 4, 2, 1];
console.log(stoneMerge(stones)); // 输出 14
```
码小课网站中有更多相关内容分享给大家学习，涵盖算法基础、进阶、以及实际面试问题解析，欢迎大家访问学习。