算法第八十题：三角形最小路径和，动态规划

#算法第八十题：三角形最小路径和，动态规划| 来源: 网络整理| 查看: 265

题目：

解法1：动态规划

思路：

初始化一个和triangle形状一模一样的dp，依照规则从顶向下地遍历，当前最优就是上一层的对应位置和上一层对应位置的前一个位置的最小值+当前位置的triangle中的值，最后返回dp最后一层的最小值即可。

# time: O(n^2) # space: O(n^2) # 执行用时：64 ms, 在所有 Python3 提交中击败了5.48%的用户 # 内存消耗：16.5 MB, 在所有 Python3 提交中击败了17.84%的用户 class Solution: def minimumTotal(self, triangle: List[List[int]]) -> int: dp = [[0 for _ in range(i)] for i in range(len(triangle)+1)][1:] dp[0][0] = triangle[0][0] for i in range(1,len(triangle)): for j in range(len(triangle[i])): if j == 0: dp[i][j] = dp[i-1][j] + triangle[i][j] elif j == len(triangle[i]) - 1: dp[i][j] = dp[i-1][j-1] + triangle[i][j] else: dp[i][j] = min(dp[i-1][j], dp[i-1][j-1]) + triangle[i][j] return min(dp[-1])

解法2：动态规划优化

思路：

每一层的dp从后往前遍历，由于每一层的元素只考虑上一层的对应位置和前一个位置，因此从后往前遍历时，可以直接覆盖当前位置的值，并不会影响之后的遍历，所以dp只需要一维list即可，优化了空间复杂度。

# time: O(n^2) # space: O(n) # 执行用时：52 ms, 在所有 Python3 提交中击败了18.34%的用户 # 内存消耗：15.8 MB, 在所有 Python3 提交中击败了75.28%的用户 class Solution: def minimumTotal(self, triangle: List[List[int]]) -> int: dp = [0 for i in range(len(triangle[-1]))] dp[0] = triangle[0][0] for i in range(1, len(triangle)): for j in range(len(triangle[i])-1, -1, -1): # 从后往前遍历 if j == 0: dp[j] = dp[j] + triangle[i][j] elif j == len(triangle[i]) - 1: dp[j] = dp[j-1] + triangle[i][j] else: dp[j] = min(dp[j], dp[j-1]) + triangle[i][j] return min(dp)

同名公众号：舟晓南

对机器学习，深度学习，python，算法题感兴趣，欢迎关注专栏，学习笔记已原创100+篇，持续更新中~ ^_^

专栏文章举例：

【机器学习】关于逻辑斯蒂回归，看这一篇就够了！解答绝大部分关于逻辑斯蒂回归的常见问题，以及代码实现 - 知乎 (zhihu.com)

【机器学习】朴素贝叶斯 -> 半朴素贝叶斯 -> 贝叶斯网络 -> 贝叶斯优化，看这一篇就够了！ - 知乎 (zhihu.com)

关于K近邻（KNN），看这一篇就够了！算法原理，kd树，球树，KNN解决样本不平衡，剪辑法，压缩近邻法 - 知乎 (zhihu.com)

专栏文章举例：

记录一下工作中用到的少有人知的pandas骚操作，提升工作效率 - 知乎 (zhihu.com)

关于切片时不考虑最后一个元素以及为什么从0开始计数的问题 - 知乎 (zhihu.com)

专栏文章举例：

算法第二十题：最长回文子串，动态规划|中心扩散法，Leetcode编号5，难度中等，字符串题 - 知乎 (zhihu.com)

算法第二十一题： Z字形变换，震荡指针，Leetcode编号6，难度中等，字符串题 - 知乎 (zhihu.com)

算法第九题：四数之和，排序暴力+排序双指针，Leetcode编号18，难度中等 - 知乎 (zhihu.com)

关于转行：

舟晓南：如何转行和学习数据分析 | 工科生三个月成功转行数据分析心得浅谈

舟晓南：求职数据分析师岗位，简历应该如何写？｜工科生三个月成功转行数据分析心得浅谈

我建了个数据分析，机器学习，深度学习的群~ 需要学习资料，想要加入社群均可私信~

在群里我会不定期分享各种数据分析相关资源，技能学习技巧和经验等等~

详情私信，一起进步吧！

写于上海 2023-04-11

【本文地址】

公司简介

联系我们

今日新闻

推荐新闻

专题文章