[数据结构与算法]2021年第十二届蓝桥杯决赛Python组（真题+解析+代码）：最小权值

1 真题

?

2 解析

难度系数：??

考察题型：动态规划

涉及知识点：DP

解题思路：

题目中的“树的权值最小可能是多少?”中的最小揭开了这道题的真正面目！DP实锤！

?DP五步：数组含义→数组赋值→遍历顺序→递推公式→打印数组

第一步：明白dp[j]的含义

 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

第四步：搞懂递推公式

谢天谢地，题目中已经给出了递推公式，直接套用就行。

?理解一下题目中的条件：结点v，有左子树L，右子树R，

如果有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