LeetCode 120. 三角形最小路径和
## 题目地址(120. 三角形最小路径和)
https://leetcode-cn.com/problems/triangle/
## 题目描述
给定一个三角形 triangle ,找出自顶向下的最小路径和。
每一步只能移动到下一行中相邻的结点上。相邻的结点 在这里指的是 下标 与 上一层结点下标 相同或者等于 上一层结点下标 + 1 的两个结点。也就是说,如果正位于当前行的下标 i ,那么下一步可以移动到下一行的下标 i 或 i + 1 。
```
示例 1:
输入:triangle = [[2],[3,4],[6,5,7],[4,1,8,3]]
输出:11
解释:如下面简图所示:
2
3 4
6 5 7
4 1 8 3
自顶向下的最小路径和为 11(即,2 + 3 + 5 + 1 = 11)。
示例 2:
输入:triangle = [[-10]]
输出:-10
```
提示:
1 <= triangle.length <= 200
triangle[0].length == 1
triangle[i].length == triangle[i - 1].length + 1
-104 <= triangle[i][j] <= 104
进阶:
你可以只使用 O(n) 的额外空间(n 为三角形的总行数)来解决这个问题吗?
## 思路
DP规划,把每一组状态存储在DP数组里面,优化空间方法是把【-2】数组的去掉,只保存【-1】和现在遍历的数组进行约简
## 代码
- 语言支持:Python3
Python3 Code:
```python
class Solution:
def minimumTotal(self, triangle: List[List[int]]) -> int:
cengNum = len(triangle)
dp = []
for i in range(cengNum):
dp.append([0]*len(triangle[i]))
dp[0][0] = triangle[0][0]
for i in range(1,cengNum):
cengList = triangle[i]
for j,val in enumerate(cengList):
## 三角形边
if j == 0:
dp[i][j] = dp[i-1][j]+val
elif j == len(cengList)-1:
dp[i][j] = dp[i-1][j-1]+val
else:#中心位置采用min算
dp[i][j] = min(dp[i-1][j-1],dp[i-1][j])+val
res = min(dp[-1])
# print(dp)
return res
if __name__ == '__main__':
triangle = [[2],[3,4],[6,5,7],[4,1,8,3]]
# triangle = [[-10]]
res = Solution().minimumTotal(triangle)
print(res)
```
**复杂度分析**
令 n 为数组长度。
- 时间复杂度:$O(n^2)$
- 空间复杂度:$O(n^2)$
相关文章
- PTA 数据结构与算法题目集(中文)7-14 电话聊天狂人 (25分) 题解
- PTA 数据结构与算法题目集(中文)7-44 基于词频的文件相似度 (30分)
- PTA 数据结构与算法题目集(中文)7-7 六度空间 (30分) 题解
- PTA 数据结构与算法题目集(中文) 7-49 打印学生选课清单 (25分)题解
- PTA 数据结构与算法题目集(中文)7-47 打印选课学生名单 (25分) 题解
- 用c语言手搓一个600行的类c语言解释器: 给编程初学者的解释器教程(1)- 目标和前言
- 用c语言手搓一个600行的类c语言解释器: 给编程初学者的解释器教程(3)- 词法分析
- 用c语言手搓一个600行的类c语言解释器: 给编程初学者的解释器教程(4)- 语法分析1:EBNF和递归下降文法
- 用c语言手搓一个600行的类c语言解释器: 给编程初学者的解释器教程(5)- 语法分析2: tryC的语法分析实现
- 用c语言手搓一个600行的类c语言解释器: 给编程初学者的解释器教程(6)- 语义分析:符号表和变量、函数
- 基于卷积神经网络的垃圾分类
- Alpha-Beta 剪枝搜索实现黑白棋AI
- flask + pyecharts 疫情数据分析 搭建交互式动态可视化新冠肺炎疫情地图(附代码实现)
- 改进的自适应中值滤波算法 去除椒盐噪声 python 代码实现
- ArcEngine + DevPress GIS二次开发:湖北疫情交互式数据分析、地图输出、专题可视化系统(含代码实现)
- 编译过程中的并行性优化(三):软件流水线化与SIMD技术
- MIT 6.828 操作系统工程 2018 fall xv6 工具链搭建与测试
- MIT 6.828 操作系统工程 lab1 2018 fall part1 & part2 笔记 and 中文注释源代码阅读
- 单细胞转录组实战03: 使用celltypist注释细胞
- MIT 6.828 操作系统工程 2018 fall lab1 part3 内核 笔记 and 中文注释源代码阅读