上图给出了一个数字三角形。从三角形的顶部到底部有很多条不同的路径。
对于每条路径，把路径上面的数加起来可以得到一个和，你的任务就是找到最
大的和。
路径上的每一步只能从一个数走到下一层和它最近的左边的那个数或者右
边的那个数。此外，向左下走的次数与向右下走的次数相差不能超过 1。
【输入格式】
输入的第一行包含一个整数 N (1 < N ≤ 100)，表示三角形的行数。下面的
N 行给出数字三角形。数字三角形上的数都是 0 至 100 之间的整数。
【输出格式】
输出一个整数，表示答案。
【样例输入】
5
7
3 8
8 1 0
2 7 4 4
4 5 2 6 5
【样例输出】
27
这是一道标准的动态规划题目，我们首先用0补全完整的数组dp(如下所示)，将数据放入数组对应的下标当中，然后，然后用dp数组去记忆从上到下路径上的值，最后再在向左下走的次数与向右下走的次数相差不能超过 1这个条件下取得的最大值，重点在于我们不能局限于这个条件，我们只需要判断我们所取值的底层的下标于顶层的下标是否相差绝对值<=1即可；
补全数组：在补全数组的过程中存在一个规律，就是第一个数据即顶部数据(该处以7为例)，下标应该为N-1，故该处的下标为4；其它数据的下标于上一层的每个下标的+1 或者 -1 得到，如3和8的下标分别为7的下标+1与-1。
dp数组记忆：在用dp去记忆时，我们得注意边界问题将其分开如当j(竖)的坐标==0或者j==2*N-2都要分开处理。
得值：我们最后只需要将j的下标范围控制在[N-2,N]之间(都是闭区间)。
Python代码：
| n = int(input()) # 输入的Nl = [] # 存储输入的值for i in range(n):l.append(list(map(int,input().split()))) # 输入数据值
dp = [[0 for _ in range(2*n-1)] for _ in range(n)] # 构建dp数组 k = n-1 # 顶部数据的下标 res = [[k]] # res用于存储各个数据的下标 for i in range(n-1): q = [] # 用于存储当前层的下标值 for i in range(len(res[-1])): q.append(res[-1][i]-1) q.append(res[-1][i]+1) # 分别-1 +1上一层的每个下标值从而得到当前下标值并保存 res.append(list(set(q))) #除去重复的下标 dp[0][k] = l[0][0] # 将顶部数据导入到相应的下标的dp数组中 for i in range(1,n): # 横向坐标 for j in range(len(l[i])): # l为存储的输入值，res为值相对于的在dp中的下标故len(l) == len(res) # 分边界处理res[i][j]为取出相应的下标， dp[i][res[i][j]]为当前的值 if j==0 : dp[i][res[i][j]] = dp[i-1][res[i][j]+1]+l[i][j] elif j>0 and j<len(l[i])-1: dp[i][res[i][j]] = max(dp[i-1][res[i][j]-1], dp[i-1][res[i][j]+1])+l[i][j] else: dp[i][res[i][j]] = dp[i-1][res[i][j]-1]+l[i][j] s = 0 for i in range(k-1, k+2): # 取值范围内取得最大值。输出 if s<dp[-1][i]: s = dp[-1][i] print(s) |
本博客主要讲述了用动态规划解决2020年python组的第8题，很纯粹的动态规划，希望对读者有所帮助。
转载请注明：XAMPP中文组官网 » Python实践操作|2020蓝桥杯之数字三角形