120. 三角形最小门路和
题目起源:力扣(LeetCode)https://leetcode-cn.com/problems/triangle
题目
给定一个三角形,找出自顶向下的最小门路和。每一步只能挪动到下一行中相邻的结点上。
相邻的结点 在这里指的是 下标 与 上一层结点下标 雷同或者等于 上一层结点下标 + 1 的两个结点。
例如,给定三角形:
[[2],
[3,4],
[6,5,7],
[4,1,8,3]
]
自顶向下的最小门路和为 11(即,2 + 3 + 5 + 1 = 11)。
解题思路
思路:递归,动静布局
首先先看题目中的提醒,【相邻的结点 在这里指的是 下标 与 上一层结点下标 雷同或者等于 上一层结点下标 + 1 的两个结点】。
咱们设 f(i, j)
为点 (i, j)
到底部的最小门路和。当初依据下面这个提醒,能够很容易失去公式:
f(i, j) = min(f(i+1, j), f(i+1, j+1)) + triangle[i][j]
也就是说,要求的门路和为:取以后结点相邻的两个结点最小值,加上以后结点的值。
递归
先尝试应用递归的办法求解,依据下面的公式,间接贴上代码:
class Solution:
def minimumTotal(self, triangle: List[List[int]]) -> int:
return self.path(triangle, 0, 0)
def path(self, triangle, i, j):
# 设置终止条件
if i == len(triangle):
return 0
# 间接应用公式
return min(self.path(triangle, i+1, j), self.path(triangle, i+1, j+1)) + triangle[i][j]
下面的代码执行超时,因为进行了大量的反复计算,当初思考进行优化。
递归(优化)
在这里,采纳建设备忘录的办法,防止反复的计算,同样这里贴上代码:
class Solution:
def minimumTotal(self, triangle: List[List[int]]) -> int:
# 备忘录
memo = {}
def path(triangle, i, j):
# 设置终止条件
if i == len(triangle):
return 0
if (i, j) in memo:
return memo[(i, j)]
memo[(i, j)] = min(path(triangle, i+1, j), path(triangle, i+1, j+1)) + triangle[i][j]
# 间接应用公式
return min(path(triangle, i+1, j), path(triangle, i+1, j+1)) + triangle[i][j]
return path(triangle, 0, 0)
下面的办法都是自顶向下的,当初咱们尝试应用动静布局,实现自底向上求解。
动静布局
应用动静布局的解法,先进行状态定义。
状态定义
设 dp[i][j]
为点 (i, j)
到底部的最小门路和。
状态转移方程
同样的,咱们依据最开始得出的公式,能够失去状态转移方程为:
dp[i][j] = min(dp[i+1][j], dp[i+1][j+1]) + triangle[i][j]
具体代码实现见【代码实现 # 动静布局】
动静布局(空间优化)
下面的动静布局算法中,咱们定义的是一个二维数组。当咱们计算 dp[i][j]
的时候,用到的是下一行的 dp[i+1][j]
和 dp[i+1][j+1]
。那咱们能够间接思考从底部往上,定义一个一维数组。
具体代码实现见【代码实现 # 动静布局(空间优化)】
代码实现
# 动静布局
class Solution:
def minimumTotal(self, triangle: List[List[int]]) -> int:
m = len(triangle)
dp = [[0] * (m+1) for _ in range(m+1)]
for i in range(m-1, -1, -1):
for j in range(0, i+1):
dp[i][j] = min(dp[i+1][j], dp[i+1][j+1]) + triangle[i][j]
return dp[0][0]
# 动静布局(空间优化)class Solution:
def minimumTotal(self, triangle: List[List[int]]) -> int:
m = len(triangle)
dp = [0] * (m+1)
for i in range(m-1, -1, -1):
for j in range(0, i+1):
dp[j] = min(dp[j], dp[j+1]) + triangle[i][j]
return dp[0]
实现后果
动静布局(优化前)
欢送关注
公众号【书所集录】