2 解析
难度系数:⭐⭐
考察题型:动态规划
涉及知识点:DP
解题思路:
题目中的“树的权值最小可能是多少?”中的最小揭开了这道题的真正面目!DP实锤!
第一步:明白dp[j]的含义DP五步:数组含义→数组赋值→遍历顺序→递推公式→打印数组
dp[i] #i:结点编号 #dp[i]:当前结点的权值第二步:给dp数组初始化赋值
dp=[float("inf")]*2022 #创建2022个结点,置无穷大 dp[0]=0 #第一个为空结点第三步:弄清dp[j]遍历的顺序
for i in range(1,2022): #遍历结点1~2021 for j in range(i): #遍历0~i第四步:搞懂递推公式
谢天谢地,题目中已经给出了递推公式,直接套用就行。
如果有i个结点,那么左子树的结点为C(L)= j ,右子树的结点为C(R)= i-j-1。
dp[i]=min(dp[i],1+2*dp[j]+3*dp[i-j-1]+j*j*(i-j-1))#递推公式第五步:打印数组
print(dp[2021]) #输出结果:2653631372
3 代码
#最小权值 dp=[float("inf")]*2022 #创建2022个结点,置无穷大 dp[0]=0 #第一个为空结点 for i in range(1,2022): #遍历结点1~2021 for j in range(i): #遍历0~i dp[i]=min(dp[i],1+2*dp[j]+3*dp[i-j-1]+j*j*(i-j-1))#递推公式 print(dp[2021]) #输出结果:2653631372
欢迎分享,转载请注明来源:内存溢出
评论列表(0条)