蓝桥杯 第五天 2021 国赛 第 5 题 最小权值
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 <2022 ; i++) {//模拟所有节点
for (int j = 0; j <i ; j++) {//模拟左子树节点
int l=j,r=i-1-j;//左节点+右节点+第一个节点=所有节点,所以r=i-j-1
dp[i]=Math.min(dp[i],1+2*dp[l]+3*dp[r]+l*l*r);
}
}
System.out.println(dp[2021]);
}
一开始除了第一项要每项的默认值为最大值,也就是这段代码
Arrays.fill(dp,Long.MAX_VALUE);
dp[0] = 0;然后默认空子树权值是0 ,也就是dp[0] = 0,然后再按照公式来进行递归,最后得到dp[i]的值