数字三角形(线性DP)
数字 DP 线性 三角形
2023-09-14 09:01:26 时间
Question
给定一个如下图所示的数字三角形,从顶部出发,在每一结点可以选择移动至其左下方的结点或移动至其右下方的结点,一直走到底层,要求找出一条路径,使路径上的数字的和最大。
7
3 8
8 1 0
2 7 4 4
4 5 2 6 5
输入格式
第一行包含整数 n,表示数字三角形的层数。
接下来 n 行,每行包含若干整数,其中第 i 行表示数字三角形第 i 层包含的整数。
输出格式
输出一个整数,表示最大的路径数字和。
数据范围
1≤n≤500,
−10000≤三角形中的整数≤10000
输入样例:
5
7
3 8
8 1 0
2 7 4 4
4 5 2 6 5
输出样例:
30
难度:简单
时/空限制:1s / 64MB
总通过数:34534
总尝试数:60828
来源:模板题, usaco training 1.6
算法标签
Ideas
线性DP
Code
# 线性DP O(N^2) 500*250
n = int(input())
lis = [[0]]
m = 0
for i in range(n):
tem_lis = [0]+list(map(int,input().strip().split()))
lis.append(tem_lis)
m = max(m,len(tem_lis))
# print(lis)
N = 510
# 因为−10000≤三角形中的整数≤10000 初始化所有值为负无穷
f = [[float('-inf') for i in range(N)] for j in range(N)]
# 走到f[1][1] 的值就是lis[1][1]
f[1][1] = lis[1][1]
for i in range(2,n+1):
for j in range(1,i+1):
f[i][j] = max(f[i-1][j-1]+lis[i][j],f[i-1][j]+lis[i][j])
# 遍历最后一层f
res = float('-inf')
for i in range(1,n+1):
res = max(res,f[n][i])
print(res)
相关文章
- 数字滤波器
- Javascript正则匹配数字,中英文,中横线,下划线,utf-8中文
- 随机生成8位的数字字符串
- C# 自定义数字格式字符串 ToString ###,###,###,##0
- C# 自定义数字格式字符串 ToString ###,###,###,##0
- 编程笔试(解析及代码实现):求不重复数字之和给定一组整型数字,里面有且仅有两个数字值出现了一次,其他的数字都出现了两次。请写出程序求出这两个只出现了一次的数字之和
- 【华为云技术分享】HDC.Cloud | 以数字资产模型为核心驱动的一站式IoT数据分析实践
- 【数字信号处理】线性时不变系统 LTI “ 输入 “ 与 “ 输出 “ 之间的关系 ( 线性卷积起点定理 | 左边序列概念 | 推理 )
- leetcode 136. 只出现一次的数字 js 实现
- opencv 仪表数字切割
- LabVIEW编程LabVIEW U16数字与布尔型数组转换例程与相关资料
- C语言之打印数字/字符ASCII(五十二)