ACM UVA 10304 (Optimal Binary Search Tree)

题目： 

思路： (递归，DP)

1. 记binary search tree的N个节点分别为 1, 2, 3, ..., N
2. 记frequency[n]为第n个节点的frequency值
3. 记sumFrequency(l,r)为从l到r的节点的frequency和。
4. 记minTreeCost(i,l,r)是root节点为i, 所有节点为l到r的BST的cost，其中l <= i <= r。
   minTreeCost(i,l,r) = minCost(l,i-1) + sumFrequency(l,i-1) + minCost(i+1,r) + sumFrequency(i+1,r)
5. 记minCost(l,r)为节点为l,l+1,l+2,...r的BST的最小cost (1 <= l,r <= N)。那么我们所求的BST的最小cost就可以表示为minCost(1,N)。可以看出，minCost(l,r)是个不变值，因此我们可以用一个数组记下来，不必重复计算，这就是DP。
   minCost(l,r) = MIN { minTreeCost(l,l,r), minTreeCost(l+1,l,r),..., minTreeCost(r,l,r) }

代码：

//
// Author: xfye
// Status: AC
//

#include <iostream>

using namespace std;

// g_cost[i][j] is the minimum cost of the binary search tree from
// i to j. This tree is the topmost tree.
int g_minNativeCost[250][250];

//
// Description
//    Get the native cost of a binary search tree whose nodes are
//    from l to r;
//
// Parameters
//    @frequency frequency array
//    @l The left index in frequency array
//    @r The right index in frequency array
//
// Return
//    Returns the minimum native cost of the tree (from l to r);
//
// Remasks
//    The tree has a native cost when the level of the root is 0.
//    The native cost of this tree (from l to r) is saved into
//    g_minNativeCost[l][r] for later using (DP).
//    The full cost of a tree is calculated like this:
//       fullCost = nativeCost + (f1 + f2 + ...fn) * level
//
//
int findMinNativeCost(int frequency[], int l, int r)
{
    if (l == r) {
        return 0;
    }

    int minNativeCost = -1;

    //
    // find the minimum cost for each tree whose root is i
    //
    for (int i = l; i <= r; i++) {
        // int nativeCost = frequency[i] * level;
        int nativeCost = 0;

        if (i != l) {
            if (g_minNativeCost[l][i-1] == -1) {
                nativeCost += findMinNativeCost(frequency, l, i-1);
                for (int k = l; k <= i-1; k++) {
                    nativeCost += frequency[k];
                }
                g_minNativeCost[l][i-1] = nativeCost;
            } else {
                nativeCost += g_minNativeCost[l][i-1];
            }
        }
        if (i != r) {
            if (g_minNativeCost[i+1][r] == -1) {
                nativeCost +=  findMinNativeCost(frequency, i+1, r);
                for (int k = i+1; k <= r; k++) {
                    nativeCost += frequency[k];
                }
                g_minNativeCost[i+1][r] = nativeCost;
            } else {
                nativeCost += g_minNativeCost[i+1][r];
            }
        }

        if (minNativeCost == -1) {
            minNativeCost = nativeCost;
        } else if (minNativeCost > nativeCost) {
            minNativeCost = nativeCost;
        }
    }

    return minNativeCost;
}

int main()
{
    int n = 0;
    int frequency[250];

    while (cin >> n) {
        for (int i = 0; i < n; i++) {
            cin >> frequency[i];
        }

        for (int i = 0; i < 250; i++) {
            for (int j = 0; j < 250; j++) {
                g_minNativeCost[i][j] = -1;
            }
        }
        cout << findMinNativeCost(frequency, 0, n-1) << endl;
    }

    return 0;
}