本题为填空题,只需要算出结果后,在代码中使用输出语句将所填结果输出即可。
对于一棵有根二叉树? T,小蓝定义这棵树中结点的权值? W(T)?如下:
空子树的权值为 0 。
如果一个结点? v?有左子树? L, 右子树? R,分别有? C(L)?和? C(R)?个结点,则? W(v)=1+2W(L)+3W(R)+(C(L))^2*C(R)
树的权值定义为树的根结点的权值。
小蓝想知道,对于一棵有?
2021?个结点的二叉树,树的权值最小可能是多少?
//动态规划
import java.util.*;
public class Main {
public static void main(String[] args) {
long[] dp=new long[2022];
Arrays.fill(dp,Long.MAX_VALUE);
dp[0]=0;
for(int i=1;i<=2021;i++){
for(int L=0;L<i;L++){
int R=i-L-1;
dp[i]=Math.min(dp[i],1+2*dp[L]+3*dp[R]+(long)Math.pow(L,2)*R);
}
}
System.out.println(dp[2021]);
}
}