题目描述补充

题目：石子归并

有一堆石子放在一排，现要求将它们归并成一堆。归并过程中，每次可以将相邻的两堆石子合并成一堆，合并的代价为这两堆石子的重量之和。试求将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代码示例

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代码示例

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代码示例

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

码小课网站中有更多相关内容分享给大家学习，涵盖算法基础、进阶、以及实际面试问题解析，欢迎大家访问学习。