最优二叉树.cpp

来自「这里面是很多经典算法的源代码」· C++ 代码 · 共 44 行

#include<stdio.h>//分清何时该用整数，何时该用 实数 
double r[]={0,0.1,0.2,0.4,0.3};
int num=4;
double dp[20][20];
double temp,min;
main()
{
	double try1(int ,int );
	min=try1(1,4);
}
double getsum(int i,int j)
{
	double sum=0;
	for(int k=i;k<=j;k++)
	{
		sum+=r[k];
	}
	return sum;
}
double try1(int i,int j)
{
	if(dp[i][j])
	{
		return dp[i][j];
	}
	if(i==j)
	{
		dp[i][j]=r[i];
		return dp[i][j];
	}
	if(i>j)
	{
		dp[i][j]=0;
		return dp[i][j];
	}
	int k;
	dp[i][j]=try1(i,j-1)+getsum(i,j);
	for(k=i;k<=j-1;k++)
	{
		temp=try1(i,k-1)+try1(k+1,j)+getsum(i,j);
		dp[i][j]=(dp[i][j]>temp?temp:dp[i][j]);
	}
	return dp[i][j];
}