very nicely done, bro.

1. You code has bugs for allocating/deallocating --- use delete []
instead of delete for arrays;
2. Your algorithm is a dynamic programming scheme and has O(n^3)
time complexity.

I am thinking about this can be done use a greedy algorithm with O(n^2)
time complexity.

3. It would be better if your soln provided the optimal soln --- this
means you need to track back where the parentheses are put.

[此贴子已经被作者于2007-7-15 14:45:27编辑过]

// 第一题， 用递归做

结果：
29786
850
+ 850
------------
31486

[此贴子已经被作者于2007-7-15 22:52:30编辑过]

/*---------------------------------------------------------------------------
File name: C76-45.cpp
Author: HJin (email: fish_sea_bird [at] yahoo [dot] com)
Created on: 7/3/2007 17:18:43
Environment: Windows XP Professional SP2 English +
Visual Studio 2005 v8.0.50727.762

Modification history:
===========================================================================

Problem statement:
---------------------------------------------------------------------------
经典 76 道编程题 之 45:

45. (数列的最小代价) 给定一个正整数序列，例如：4,1,2,3, 不改变数的位置把
它们相加， 并且由括号来标记每一次加法所得到的和。例如：((4+1)+(2+3))=
((5)+(5))=10. 除去原数4、1、2、3之外，其余都为中间结果，如：5,5,10, 将中
间结果相加，得到：5+5+10=20, 数 20 称为此数列的一个代价。对于另一种算法:
(4+((1+2)+3))=(4+((3+3))=(4+(6))=10, 得到数列的另一个代价为：3+6+10=19.
若给出 N 个数的数列，求出此数列的最小代价。

Analysis:
---------------------------------------------------------------------------
The minimum sequence price (SMP) problem:

For n numbers a_1 ... a_n, we need to do n-1 additions, thus there are
n-1 intermediate results. Our goal is to make the sum of these n-1
intermediate results as small as possible.

Let P_{i..j} be the sub-problem for a_i ... a_j, 1<=i <=j <=n, and m[i, j]
the corresponding minimum price. Then

m[i, j] = 0, if i=j; (1)
= min_{i<=k<j} { m[i, k], m[k+1, j]} + (a_i + ... + a_j)
if i<j.

Note that the formula (1) is very similar to the matrix chain order problem
introduced on CLRS [2]'s book.

m[1, n] gives the minimum price for a_1 .... a_n. To track back where we should
put the parentheses, we use another matrix to keep record of the k which minimizes
the equation in (1).

Sample output:
---------------------------------------------------------------------------
Optimal solution is:
(4+((1+2)+3))
Minimum sequence price is 19.
Press any key to continue . . .

Optimal solution is:
(((((1+2)+3)+(4+5))+(6+7))+((8+9)+10))
Minimum sequence price is 173.
Press any key to continue . . .

Optimal solution is:
(((1+-2)+(9+-3))+10)
Minimum sequence price is 25.
Press any key to continue . . .

Reference:
---------------------------------------------------------------------------

1. 野比, [全民编程]76道高难度C++练习题
http://bbs.bc-cn.net/viewthread.php?tid=147967

2. CLRS, introduction to algorithms, 2nd ed, MIT press.

*/

#include <iostream>
using namespace std;

#define INFPos (~(1<<31))
#define DIM(a) sizeof( (a) ) / sizeof ( (a)[0] )

/** Implement formula (1).

O(n^3) time + O(n^2) space.
*/
int smp(int*a, int n);

/**
Print the optimal solutions (the parentheses) recursively.
*/
void printOptSoln(int**s, int*a, int i, int j);

template <class T>
T** new2dInit(int row, int col)
{
T** arr2d = new T*[row];
int i;
int j;

for(i=0; i<row; ++i)
{
arr2d[i] = new T[col];
}

for(i=0; i<row; ++i)
{
for(j=0; j<col; ++j)
{
arr2d[i][j] = T();
}
}

return arr2d;
}

template <class T>
void delete2d(T** arr2d, int row)
{
for(int i=0; i<row; ++i)
{
delete [] arr2d[i];
}

delete [] arr2d;
}

int main()
{
// test #1
int a[] = {4, 1, 2, 3};
smp(a, DIM(a));

// test #2
//int a[] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
//smp(a, DIM(a));

// test #3 --- numbers can be negative
//int a[] = {1, -2, 9, -3, 10};
//smp(a, DIM(a));

return 0;
}

int smp(int*a, int n)
{
int** m;
int** s;

int i;
int j;
int k;
int l; // length of a subproblem P_{i..j}
int q;
int sum; // a_i + ... + a_j

m = new2dInit<int>(n, n);
s = new2dInit<int>(n, n);

for (l=2; l<=n; ++l)
{
for (i=0; i<=n-l; ++i)
{
j = i+l-1;

// assign m[i,j] to be \+inf
m[i][j] = INFPos;

/**
This sum has been repeatedly calculated.

You could use another 2d buffer to store the
results. The situation is that we have two choices here:

choice #1: 3n^2 space + n^3 time (allocate a new 2d buffer for the sums)
choice #2: 2n^2 space + 2n^3 time.

As implemented, we are using choice #2.
*/
sum = 0;
for (k=i; k<=j; ++k)
{
sum += a[k];
}

for (k=i; k<j; ++k)
{
// implement (1)
q = m[i][k] + m[k+1][j] + sum;
if ( m[i][j] > q )
{
m[i][j] = q;
s[i][j] = k;
}
}
}
}

cout<<"Optimal solution is:\n";
printOptSoln(s, a, 0, n-1);

j = m[0][n-1]; // reuse j to keep m[0][n-1]

cout<<"\nMinimum sequence price is "<<j<<"."<<endl;

// free memory
delete2d<int>(m, n);
delete2d<int>(s, n);

return j;
}

void printOptSoln(int** s, int*a, int i, int j)
{
if(i==j)
{
cout<<a[i];
}
else
{
cout<<"(";
printOptSoln(s, a, i, s[i][j]); // i..k
cout<<"+";
printOptSoln(s, a, s[i][j]+1, j); // k+1..j
cout<<")";
}
}

[此贴子已经被作者于2007-7-17 10:47:58编辑过]

[此贴子已经被作者于2007-7-17 10:59:22编辑过]

７６道完整版有答案没？