五、在一个操场上一排地摆放着N堆石子，N 子号为1，2...，N。现要将石子有次序地合并成一堆。每堆石子包含的石子个数给定，规定每次只能选相邻的2堆石子合并成新的一堆，并将新的一堆石子数记为该次合并的得分。(1)设要求计算出将堆石子合并成一堆的最小得分值，已知该问题可以采用动态规划来进行求解，试写出你的动态规划算法的递归方程，并分析该递归方程能否采用递归程序来实现; (2一个(代小 分;(3)第(2时间(4)如果要得到取得最得分的合并方案，将如修改，使之能够输出最优的合并方案，并分析该输出方法的空间复杂度(注意最合并方案的表示可以采用加括号的方式表示)。

首先，我们定义一个函数 $f(i,j)$ 表示将第 $i$ 堆到第 $j$ 堆石子合并成一堆所需的最小得分值，其中 $1\leq i \leq j \leq N$。则原问题的最终解为 $f(1,N)$。对于每一次合并，我们可以将石子分成两部分，一部分是第 $i$ 堆到第 $k$ 堆的石子，另一部分是第 $k+1$ 堆到第 $j$ 堆的石子。则该次合并所得的得分为两部分的得分之和再加上这两部分合并的得分，即$f(i,j)=f(i,k)+f(k+1,j)+sum_{p=i}^j w_p$，其中 $sum_{p=i}^jw_p$ 表示第 $i$ 堆到第 $j$ 堆石子的总数。因此，我们可以得到递归方程为：
$$
f(i,j)=\begin{cases}
0 & ,i=j \\
\min_{i\leq k<j}\{f(i,k)+f(k+1,j)+sum_{p=i}^j w_p\} & ,i<j \\
\end{cases}
$$
该递归方程可以采用递归程序来实现，但是由于递归调用会产生大量的重复计算，因此我们需要采用记忆化搜索或者动态规划的方式来避免重复计算，提高算法的效率。

对于第二个问题，要求计算出最小得分值，可以采用动态规划的方式来求解。我们可以使用一个二维数组 $dp$，其中 $dp[i][j]$ 表示将第 $i$ 堆到第 $j$ 堆石子合并成一堆所需的最小得分值。根据递推方程，我们可以得到动态规划的状态转移方程：
$$
dp[i][j]=\begin{cases}
0 & ,i=j \\
\min_{i\leq k<j}\{dp[i][k]+dp[k+1][j]+sum_{p=i}^j w_p\} & ,i<j \\
\end{cases}
$$
最终的解为 $dp[1][N]$。

对于第三个问题，要求输出最优的合并方案，我们可以使用一个二维数组 $s$，其中 $s[i][j]$ 表示将第 $i$ 堆到第 $j$ 堆石子合并成一堆所得到的最小得分值的分割点 $k$。同时，我们可以使用一个字符串 $ans$ 来记录最优的合并方案。具体的，我们可以定义一个函数 $print(i,j)$ 来实现输出最优合并方案的功能，其中 $print(i,j)$ 表示输出将第 $i$ 堆到第 $j$ 堆石子合并成一堆所得到的最优合并方案。递归地进行如下操作：

1. 如果 $i=j$，则将第 $i$ 堆石子的编号添加到 $ans$ 中。

2. 如果 $i<j$，则根据 $s[i][j]$ 分割点的位置，将合并过程分成两部分，分别递归调用 $print(i,k)$ 和 $print(k+1,j)$，并在 $ans$ 中插入括号。

具体的，我们可以采用如下的代码来实现：

void print(int i, int j) {
    if(i == j) {
        ans += to_string(i);
        return;
    }
    ans += "(";
    int k = s[i][j];
    print(i, k);
    ans += ",";
    print(k+1, j);
    ans += ")";
}

由于需要输出最优的合并方案，因此需要记录 $s$ 数组来保存分割点的位置，同时需要使用字符串 $ans$ 来保存最优合并方案。因此，输出最优合并方案的空间复杂度为 $O(N^2)$。