蓝桥杯动态规划实战：从数字三角形到砝码称重

适合人群：蓝桥杯备考生 | 算法竞赛入门者 | DP学习实践者

一、我的动态规划入门之路

1. 数字三角形：经典DP首战告捷

2. 砝码称重：背包问题的变形

二、蓝桥杯高频算法考点

三、蓝桥杯DP专项训练题

四、备考建议

一、我的动态规划入门之路

1. 数字三角形：经典DP首战告捷

题目描述：

从三角形的顶部到底部有很多条不同的路径。对于每条路径，把路径上面的数加起来可以得到一个和，你的任务就是找到最大的和（路径上的每一步只可沿左斜线向下或右斜线向下走）。

输入描述:
- 输入的第一行包含一个整数N（1≤N≤100)，表示三角形的行数。
- 下面的N行给出数字三角形。
(数字三角形上的数都是0至99之间的整数。)输出描述:
- 输出一个整数，表示答案。

解题思路：

我们可以先假象一个两层的三角形：

 1
2 3

这个时候是：1 -> 3 这时候1+3=4便是最大的路径。把这个三角形扩充到三层：

  65 1
4 2 3

此时6 -> 5 -> 4 这条路径是最大的了，但是当数字杂乱且层数多的时候就不方便找出来啦。

所以我们可以这样想，怎么把三层四层甚至多层的三角形变成两层三层的三角形。

1. 我们把最后两层换成一堆小三角形，并将最大的一个将在上一层上，如：

  65 1
4 2 3
#################5     |  1
4 2    | 2 34->5最大;3->1最大。
故而三层的三角形可以简化为：6
9 4
这样便是两层的三角形了

也就是自底向上，代码如下：

def db(li1,li2):for i in range(len(li1)):if li1[i] +li2[i] >= li1[i] +li2[i+1]:li1[i] += li2[i]else:li1[i] += li2[i+1]return li1# 请在此输入您的代码
triangle = []
n = int(input())
# 读取每一行的数字
for i in range(n):row = list(map(int, input().split()))  # 将输入的字符串分割并转换为整数列表triangle.append(row)# 问题处理
for k in range(n-1):x = db(triangle[n-1-k-1],triangle[n-1-k])triangle[n-1-k-1] = xprint(triangle[0][0])

2. 我们也可以把最顶层的数加到下一层，然后又将第二层加到第三层，在比较最后一层最大的数，如：

  65 1
4 2 36->5  |  6->1
-------------------11  7
4  2  311->4,11->2  |  7->2,7->3
显然11>7，所以11和7都能达到的2应该选1115 13 10 --> 15最大

自顶向下的方法，代码如下：

def main():import sysinput = sys.stdin.read().split()idx = 0n = int(input[idx])idx += 1# 读取数塔的每一层arr = []for i in range(n):row = list(map(int, input[idx:idx+i+1]))arr.append(row)idx += i + 1# 初始化动态规划数组dp = [[0]*(i+1) for i in range(n)]dp[0][0] = arr[0][0]# 动态规划填表for i in range(1, n):for j in range(i+1):if j == 0:# 只能来自上一层的左边dp[i][j] = dp[i-1][j] + arr[i][j]elif j == i:# 只能来自上一层的右边dp[i][j] = dp[i-1][j-1] + arr[i][j]else:# 可以来自上一层的左边或右边，取最大值dp[i][j] = max(dp[i-1][j-1], dp[i-1][j]) + arr[i][j]# 找到最后一层的最大值max_val = max(dp[-1])print(max_val)if __name__ == "__main__":main()

2. 砝码称重：背包问题的变形

题目描述：给定砝码重量，求能称出的不同重量数（蓝桥杯2021省赛题）。

解题思路：

天平分左右两边，我们假设左边放砝码减重量，右边是增；同时每一个砝码只能使用一次；砝码总重量不超过100000。

所以我们可以假定砝码之和为能得到的最大重量，初始时天平的重量为0；我们可以通过：

0 + 1 代表右边放砝码1的情况
0 - 1 代表左边放砝码1的情况
-------------------------------
1 + 3 代表右边放砝码1 + 砝码3的情况
1 - 3 代表右边放砝码1,左边放砝码3的情况

由于左右只差称出的重量是一致的，所以我们在出现负值时，可以用abd取绝对值转为正的，或者改为重的减轻的(3-1)来变换，代码如下：
代码片段：

def bg(num_list):max_wight = sum(num_list)bag = [False] * (max_wight + 1) # 0~砝码总重的重量bag[0] = True # 称出初始为0for w in num_list:# 使用临时数组来避免重复更新new_bag = bag[:]for i in range(max_wight, -1, -1):if bag[i]:if i + w <= max_wight:new_bag[i + w] = Trueif i - w >= 0:new_bag[i - w] = Trueif w - i >=0:new_bag[w - i] = True# 更新原数组为新的状态bag = new_bag# print(bag)# 计算所有可以表示的重量数量count = 0for i in range(max_wight + 1):if bag[i]:count += 1return count - 1  # 排除0这个状态n = int(input())
num_list = list(map(int, input().split()))
result = bg(num_list)
num_list.sort(reverse=True)
# print(num_list)
print(result)
# 6 0
# 10 2 4 6 0
# 9 10 11 1 2 3 4 5 6 7 0

二、蓝桥杯高频算法考点

算法类型	常见题型	例题编号
贪心算法	区间调度、最小生成树	蓝桥杯2020省赛：合并果子
DFS/BFS	迷宫问题、连通块计数	蓝桥杯2019国赛：迷宫
并查集	动态连通性、朋友圈问题	蓝桥杯2021省赛：合根植物
前缀和	子矩阵和、差分数组应用	蓝桥杯2022省赛：统计子矩阵
二分查找	最大值最小化、有序数据查找	蓝桥杯2021国赛：分巧克力