石子合并问题动态规划解题思路

石子合并问题是一个经典的动态规划问题，其解题思路如下：
1. 定义状态：设dp[i][j]表示将第i堆到第j堆石子合并成一堆所需要的最小代价。
2. 初始化状态：当i=j时，dp[i][j]=0，因为一堆石子不需要合并。
3. 状态转移方程：对于dp[i][j]，枚举其区间内的所有断点k，将其分为dp[i][k]和dp[k+1][j]两部分，再加上合并这两部分的代价sum[i][j]，即可得到dp[i][j]的值，即dp[i][j]=min(dp[i][j], dp[i][k]+dp[k+1][j]+sum[i][j])。
4. 最终答案：dp[n]即为将所有石子合并成一堆的最小代价。

下面是Python代码实现：

n = 4
stones = [4, 4, 5, 9]
dp = [[0] * n for _ in range(n)]
sums = [0] * (n+1)
for i in range(1, n+1):
    sums[i] = sums[i-1] + stones[i-1]
for len_ in range(2, n+1):
    for i in range(1, n-len_+2):
        j = i + len_ - 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]+sums[j]-sums[i-1])
print("将所有石子合并成一堆的最小代价为：", dp[1][n])