root[i, j]——顶点i..顶点j所组成的子树达到最大分值时的根编号。当i = j时，root[i, i] := i。

由于问题没有明显的阶段特征，而是呈现为非线性的树形结构，因此，我们采用后序遍历的顺序来计算状态转移方程。计算过程如下：

【参考程序片段】{cpp版}

​
long long search(int L, int r)    // 递归计算f[L][r]
{
int  k;
long long  now, ans;    // 当前分值
if (L > r) return 1;
if (f[L][r]== -1)     // 若尚未计算出顶点L..顶点r对应子树的最高分值
   for(k=L; k<=r; k++) {     // 穷举每一个可能的子根k
      now = search(L, k-1) * search(k+1, r) + f[k][k];  
// 计算以k为根的子树的分值
      if(now > f[L][r])  {
//若该分值为目前最高，则记入状态转移方程，并记下子根}
          f[L][r] = now; 
root[L][r] = k;
      }
}
return  f[L][r];   {返回顶点L..顶点r对应子树的最高分值}
}
 
​

【参考程序】{Pascal版} function search(L, r: integer) : int64; {递归计算f[L. r]}

​
var
  i: integer;
  now: int64;   {当前分值}
begin
  if L > r then search := 1
  else 
begin
      if f[L, r] = -1 then {若尚未计算出顶点L..顶点r对应子树的最高分值}
        for i := L to r do  {穷举每一个可能的子根i}
          begin
            now := search(L, i-1) * search(i+1, r) + f[i, i];  {计算以i为根的子树的分值}
            if now > f[L, r] then  {若该分值为目前最高，则记入状态转移方程，并记下子根}
              begin
                f[L, r] := now; way[L, r] := i;
              end;
        end;  {for}
        search := f[L, r];   {返回顶点L..顶点r对应子树的最高分值}
    end;   {else}
end;  {search}
 
​

显然，主程序可以通过递归调用search(1, n)来计算最高分值。算法的时间复杂度为O(n^2)。

【任务二】输出加分二叉树的前序遍历

递归调用search(1, n)后得出的way给出了加分二叉树的结构，其中way[i, j]为该树中顶点i..顶点j的根序号。由于二叉树中序遍历的顺序为1..n，因此，1..way[i, j]-1为左子树，way[i, j] + 1 .. j为右子树。现按照根→左子树→右子树的顺序对加分二叉树进行前序遍历。

注意：由于数字之间用空格隔开，而第一个数字前没有空格，因此，设firstwrite为首数字标志。一旦输出了第一个数字，firstwrite设为false，表明在输入新的数字前需要加空格。

由此，得出前序遍历加分二叉树的算法：

【参考程序片段】{CPP版}

​
// 前序遍历顶点L..顶点r对应的子树
void  preorder(int L, int r)
{
if (L > r)  return;
if (firstwrite)
firstwrite = false;
else
  cout<<‘ ‘;      // 顶点间用空格分开
cout << root[L][r];             // 输出子树的根
preorder(L, root[L][r]-1);     // 前序遍历左子树
preorder(root[L][r]+1, r);     // 前序遍历右子树
}
 
​

【参考程序片段】{Pascal版}

​
procedure  preorder(L, r: integer);
// 前序遍历顶点L..顶点r对应的子树
begin
   if L > r then exit;
   if firstwrite then
       firstwrite := false
   else
       write(‘ ‘);   {顶点间用空格分开}
   write(way[L, r]);   {输出子根}
   preorder(L, way[L, r] - 1);   {前序遍历左子树}
   preorder(way[L, r] + 1, r);   {前序遍历右子树}
end;
 
​

【任务三】主程序 有了search函数和preorder过程，就不难得出主程序了：

『Cpp』

​
​
int main()
{
int n, i;
bool  firstwrite;
cin >> n;    // 读顶点数
for(i=1; i<=n; i++)      // 状态转移方程初始化
  for(j=i; j<=n; j++)
    f[i][j] = -1;
for (i=1; i<=n; i++) {
  cin >> f[i][i];       // 读顶点i的分值
  root[i][i] = i;        // 顶点i单独成一棵子树
   }
cout << search(1, n) << endl;      // 计算和输出最高加分
firstwrite = true;                   // 设立首顶点标志
preorder(1, n);                       // 前序遍历二叉树
return 0;
}
 
​
 
​

『Pascal』

​
​
​
read(n);  {读顶点数}
for i := 1 to n do   {状态转移方程初始化}
  for j := i to n do
    f[i j] := -1;
for i := 1 to n do
  begin
    read(temp);   {读顶点i的分值}
    f[i, i] := temp;  way[i, i] := i;   {顶点i单独成一棵子树}
  end;
writeln(search(1, n));   {计算和输出最高加分}
firstwrite := true;     {设立首顶点标志}
preorder(1, n);    {前序遍历二叉树}
writeln;
 
​
 
​
 
​

以上算法采用了自上而下的记忆化方法，即程序流程基本按照原问题的递归定义，不同的是，它专门设置了一张表way，用来记忆在求解过程中得出的所有子树的根，以便在前序遍历中使用。 另外，当在递归过程中第一次遇到一个子问题（f[L, r]=-1）时，计算其解，以后每遇到该子问题时，就不重复计算f[L, r]了。记忆化方式有着只解那些肯定要解的子问题的优点。_在应用动态规划方法求解非线性结构问题时，一般采用自上而下的记忆化方法_。