2021年第十二届蓝桥杯决赛Python组（真题+解析+代码）：最小权值_python构建一个权值最小的数组

1 真题

2 解析

难度系数：⭐⭐

考察题型：动态规划

涉及知识点：DP

解题思路：

题目中的“树的权值最小可能是多少?”中的最小揭开了这道题的真正面目q(≧▽≦q)

DP实锤！下面请欣赏：如何用5行代码秒杀这道题？

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

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

 dp[i]　#i:结点编号 #dp[i]:当前结点的权值

第二步：给dp数组初始化赋值

dp=[0]+[float("inf")]*2021 #空结点+2021个无穷大结点

第三步：弄清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=[0]+[float("inf")]*2021  #空结点+2021个无穷大结点
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

DP模板

#模板
dp=[]*(n+1)                             #1.dp数组初始化      
dp[x]=[]                                #2.特殊值赋值
for i in range():                       #3.循环遍历
  for j in range():
    dp[j]=min(dp[j],dp[i]+abc(i,j))     #4.递推公式
print(dp[n])                            #5.打印数组