最优二叉查找树-optimal binary search tree-dynamic programming

//最优二叉查找树-optimal binary search tree-dynamic programming
//tree node 1,2,..,n
//freq w1,w2,..,wn
//dp[i][j]->cost of subtree formed by i,i+1,..,j, inclusive
#include <stdio.h>
#include <float.h>
#define N 7
#define min(a,b) ((a) < (b) ? (a) : (b)) 
#define max(a,b) ((a) > (b) ? (a) : (b)) 
double dp[N+1][N+1];
double w_acc[N+1][N+1];//w_acc[i][j] = w[i] + w[i + 1] + .. + w[j]
/* compute w_acc ，即连续若干node的频率之和*/
void preprocess(){
    double w[] = {0, .05, .4, .08, .04, .1, .1, .23};//w[1..7], first 0 not used
    for (int i = 1; i <= N; i++) {
        w_acc[i][i - 1] = 0;
        for (int j = i; j <= N; j++) {
            w_acc[i][j] = w_acc[i][j - 1] + w[j];
        }
    }
}
void obst()
{
    for (int i = 1; i <= N; i++) {
        dp[i][i - 1] = 0;
    }
    for(int k = 0; k <= N - 1; k++){//k = j - i, node[i..j]
        for(int i = 1; i <= N - k; i++){
            int j = i + k;
            dp[i][j] = DBL_MAX;
            for(int r = i; r <= j; r++){//possible positions of root 
                dp[i][j] = min(w_acc[i][j]+dp[i][r - 1] + dp[r+1][j], dp[i][j]);
            }
        }
    }
}
int main(int argc, const char *argv[])
{
    preprocess();
    obst();
    printf("%lf\n", dp[1][N]);
    return 0;
}