Acwing.282 石子合并(动态规划)

**石子合并**

**题目描述**

有 n 个石子排列在一条线上，每个石子的大小为 a1, a2, ..., an。我们可以将两个相邻的石子合并成一个新的石子，其大小为 a1 + a2。合并的次数最多为 k 次，我们需要找到合并后石子的最大大小。

**动态规划**

这个问题可以使用动态规划来解决。我们定义一个一维数组 dp，dp[i] 表示在 i 次合并后石子的最大大小。

**状态转移方程**

对于每个石子 a_i，我们有两种选择：

1. 不合并该石子：此时石子的大小仍然是 a_i。
2. 合并该石子与前一个石子：此时石子的大小为 a_i + a_{i-1}。

因此，状态转移方程可以写成：

dp[i] = max(dp[i-1], dp[i-1] + a_i)

**初始条件**

初始条件是当 i=0 时，dp[0]=0，因为没有石子时最大大小为0。

**代码实现**

def stone_game(n, k, stones):
 # 初始化动态规划数组 dp = [0] * (n +1)
 # 初始化前 n 个石子的最大大小 for i in range(1, n +1):
 dp[i] = max(dp[i-1], dp[i-1] + stones[i-1])
 # 返回在 k 次合并后石子的最大大小 return dp[n]

n =5k =2stones = [2,3,4,5,6]
print(stone_game(n, k, stones)) # 输出:14