这道题的大概意思是，给一个数字构成的三角形，要求找出一条路径使得路径数字之和最小。
比如下面这个三角形的数字和最小的路径就是2+3+5+1=11
[
[2],
[3,4],
[6,5,7],
[4,1,8,3]
]
用T表示三角形对应的二维数组，dp表示当前行各个位置上的路径最小和，采用从底向上的计算方式，可以得到递推公式为dp[j] = T[i][j] + min(dp[j], dp[j + 1])，其中i代表行，j代表列。
def minimumTotal(self, triangle):
dp = triangle[-1]
for i in range(len(triangle) - 2, -1, -1):
for j in range(i + 1):
dp[j] = triangle[i][j] + min(dp[j], dp[j + 1])
return dp[0]
还算简单。
这道题的大概意思是，给一个数字构成的三角形，要求找出一条路径使得路径数字之和最小。 比如下面这个三角形的数字和最小...
原题地址 https://leetcode.com/problems/triangle/description/ ...
120.Triangle 题目描述 Given a triangle, find the minimum path...
LeetCode 16[M] LeetCode 17[M] LeetCode 926
leetcode leetcode to practice leetcode ac code 数组专题 done ...
【LeetCode】Fizz Buzz 解题报告 [LeetCode] https://leetcode.com/...
【LeetCode】Fizz Buzz 解题报告 [LeetCode] https://leetcode.com/...
Leetcode python answers for leetcode
Q1:leetcode 622Q2:leetcode 259Q3:leetcode 15Q4:leetcode 1...
LeetCode 传送门 https://leetcode.com/ LeetCode 题解 Github：htt...
本文标题：Leetcode 120.Triangle
本文链接：https://www.haomeiwen.com/subject/wweviftx.html
网友评论